Lower Bounds for Shellsort (thesis)

Abstract:

Shellsort is a simple classic algorithm that runs competitively on both mid-sized and nearly sorted files. It uses an increment sequence, the choice of which can drastically affect the algorithm's running time. Since we would like an optimal sorting algorithm and a trivial lower bound for Shellsort is
N* x(# of increments), we require that the size of the increment sequence is
O(log N), where N is the size of the file to be sorted. These increment sequences also tend to perform the best in practice, because of this lower bound. For some time, the complexity of Shellsort was thought to be well understood, but Sedgewick was able to provide an increment sequence that lowered the upper bound, and then Incerpi and Sedgewick extended the result to give an even better upper bound. In both papers, the authors left as open the problem of whether their bounds were tight. We prove that Sedgewick's bound is tight by analyzing the time required to sort a particularly bad permutation. Extending this proof technique seems to lead to a lower bound that matches the upper bound of Incerpi and Sedgewick for not only their increment sequence, but also for a wide class of other increment sequences. Additionally, we show that
the permutations which make Shellsort run slowly are counterexamples to a conjecture that shaker-sort, a network sorting algorithm proposed by Incerpi and Sedgewick, runs in O(N log N) time, again for a large class of increment sequences, including all those that have thus far been proposed.