Analyzing variants of Shellsort.
Information Processing Letters,
Download from publisher | BibTeX | MathSciNet
We consider two variants of Shellsort — Dobosiewicz sort and Shaker
sort. Not much is known about the running time of these algorithms. We
prove that the worst-case time of Shaker sort is O(n^(3/2) log^3 n)
for certain sequences of increments and the average-case time for both
variants is Omega(n^2/c^p) where p is the number of increments and c=2
for Dobosiewicz sort and c=4 for Shaker sort. In our proofs we adapt
techniques and results from analysis of Shellsort.