Publication details

Bronislava Brejova. Analyzing variants of Shellsort. Information Processing Letters, 79(5):223-227. September 2001.
Download from publisher | BibTeX | MathSciNet

Abstract

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.