Shellsort with three increments

DOI10.1002/(SICI)1098-2418(199701/03)10:1/2%3C125::AID-RSA6%3E3.0.CO;2-XMaRDI QIDQ3122909zbMATH OpenOpenAlexWikidataFDO

Authors Svante Janson, Donald E. Knuth

Publication date 7 August 1997

Full work available at URL https://arxiv.org/abs/cs/9608105

zbMATH Keywords

shellshort

Mathematics Subject Classification ID

Searching and sorting (68P10)

Abstract: A perturbation technique can be used to simplify and sharpen A. C. Yao's theorems about the behavior of shellsort with increments $(h,g,1)$. In particular, when $h=Theta(n^{7/15})$ and $g=Theta(h^{1/5})$, the average running time is $O(n^{23/15})$. The proof involves interesting properties of the inversions in random permutations that have been $h$-sorted and $g$-sorted.

Recommendations

• Shellsort with a constant number of increments
• On the average-case complexity of Shellsort
• A new upper bound for Shellsort
• scientific article; zbMATH DE number 1839436
• Improved upper bounds on Shellsort

Cited in

(2)

• Interview with Don Knuth
• Stochastic analysis of Shell Sort

This page was built for publication: Shellsort with three increments

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3122909)