Tight Lower Bounds for Shellsort

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. Due to the results of Pratt, the running time of Shellsort was long thought to be theta(N3/2) for
increment sequences that are "almost geometric," however, recent results have lowered the upper bound substantially, although the new bounds were not known to be tight. In this paper, we show that an increment sequence given by Sedgewick is theta(N4/3) by analyzing the time required to sort a particularly
bad permutation. Extending this proof technique to various increment sequences seems to lead to lower bounds that in general always match the known upper bounds and suggests that Shellsort runs in theta(N1+epsilon/sqrt log N) for increment sequences of practical interest, and that no increment sequence exists
that would make Shellsort optimal.