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.