Today I read a paper titled “Shellsort with three increments”

The abstract is:

* 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.*