Improved lower bounds for Shellsort
C. Gregory Plaxton, Bjorn Poonen, Torsten Suel · 1992
The authors give improved lower bounds for Shellsort based on a new and relatively simple proof idea. The lower bounds obtained are both stronger and more general than the previously known bounds. In particular, they hold for nonmonotone increment sequences and adaptive Shellsort algorithms, as well as for some recently proposed variations of Shellsort.>