A Lower Bound on the Size of Shellsort Sorting Networks
Robert Cypher · SIAM Journal on Computing · 1993
Shellsort is a sorting algorithm that is based on a set of parameters called increments. Shellsort has been used both as a sequential sorting algorithm and as a sorting network. The central result of this paper is that all Shellsort sorting networks based on monotonically decreasing increments require $\Omega (N\log ^2 {N / {\log \log N}})$ comparators. Previously, only the trivial $\Omega (N\log N)$ bound was known for this class of networks. The lower bound obtained in this paper nearly matches the upper bound of $O(N\log ^2 N)$ that was proven by Pratt.