Title :
Improved lower bounds for Shellsort
Author :
Plaxton, C. Greg ; Poonen, Bjorn ; Suel, Torsten
Author_Institution :
Dept. of Comput. Sci., Texas Univ., Austin, TX, USA
Abstract :
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
Keywords :
search problems; sorting; Shellsort; lower bounds; nonmonotone increment sequences; proof idea; Mathematics; Partitioning algorithms; Sorting; Upper bound;
Conference_Titel :
Foundations of Computer Science, 1992. Proceedings., 33rd Annual Symposium on
Conference_Location :
Pittsburgh, PA
Print_ISBN :
0-8186-2900-2
DOI :
10.1109/SFCS.1992.267769
