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 =θ (h1/5), the average running time is O(n23/15). The proof involves interesting properties of the inversions in random permutations that have been h-sorted and g-sorted.
%0 Journal Article
%1 svante97
%A Janson, Svante
%A Knuth, Donald E.
%D 1997
%I Wiley
%J Random Structures & Algorithms
%K algorithm shellsort sorting
%N 1-2
%P 125--142
%R 10.1002/(SICI)1098-2418(199701/03)10:1/2<125::AID-RSA6>3.0.CO;2-X
%T Shellsort with Three Increments
%V 10
%X 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 =θ (h1/5), the average running time is O(n23/15). The proof involves interesting properties of the inversions in random permutations that have been h-sorted and g-sorted.
@article{svante97,
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 =θ (h1/5), the average running time is O(n23/15). The proof involves interesting properties of the inversions in random permutations that have been h-sorted and g-sorted. },
added-at = {2016-11-08T04:36:22.000+0100},
author = {Janson, Svante and Knuth, Donald E.},
biburl = {https://www.bibsonomy.org/bibtex/2a7ecf7eefef9d1a718009b8657df3bca/ytyoun},
doi = {10.1002/(SICI)1098-2418(199701/03)10:1/2<125::AID-RSA6>3.0.CO;2-X},
interhash = {b3c2810f98b1ceff87f123831380caeb},
intrahash = {a7ecf7eefef9d1a718009b8657df3bca},
issn = {1098-2418},
journal = {Random Structures \& Algorithms},
keywords = {algorithm shellsort sorting},
number = {1-2},
pages = {125--142},
publisher = {Wiley},
timestamp = {2016-11-08T08:48:53.000+0100},
title = {Shellsort with Three Increments},
volume = 10,
year = 1997
}