%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 }