Shellsort with three increments
<|reference_start|>Shellsort with three increments: 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.<|reference_end|>
@article{janson1996shellsort,
    title={Shellsort with three increments},
    author={Svante Janson and Donald E. Knuth},
    journal={Random Structures Algorithms 10 (1997), no. 1-2, 125--142},
    year={1996},
    number={Knuth migration 11/2004},
    archivePrefix={arXiv},
    eprint={cs/9608105},
    primaryClass={cs.DS}
}