When More Generators Hurt: Shellsort on Full Product Grids

Abstract

Shellsort repeatedly runs insertion sort with decreasing gaps, so its worst-case cost depends on the gap sequence. Pratt's $2^u{3}^v$ sequence, one of the few systematic constructions with a proven $O(n{\log }^{2}n)$ bound, includes every product below $n$ of two base numbers, or generators. We ask whether adding more base numbers, and thus more intermediate gaps, can improve this full product grid. We show that it cannot when every product is retained and each base is at most a fixed power of the smallest. With $r$ independent bases (different exponent choices give different products) and $\Theta (\log n)$ gaps, the best possible worst-case cost is $n\exp (\Theta ((\log n{)}^{1-1/r}))$. Thus two bases give the exponent $\sqrt{\log n}$, whereas three give $(\log n{)}^{2/3}$: more bases are worse. With a budget of $p$ gaps, matching bounds give the factor $\exp (\Theta (\log n/p^{1/r}))$ beyond linear cost. The reason is simple. Few products force the smallest base $m$ to be large, and fullness makes $m$ the next-to-last gap. An input built from reversed blocks is already sorted for every earlier gap, forcing $\Omega (nm)$ work in the final pass. Powers of distinct primes give a matching construction. For arbitrary gaps, we count current-gap multiples that earlier gaps cannot form. This gives upper and lower bounds for individual passes. A Fourier argument gives necessary conditions for small total cost, while short nonnegative sums give sufficient conditions. In both settings, useful distances must be available before they are needed.