Improved lower bounds for Shellsort
- 1 January 1992
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 1, 226-235
- https://doi.org/10.1109/sfcs.1992.267769
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
This publication has 12 references indexed in Scilit:
- Short Note: Empirical study of the expected running time of ShellsortThe Computer Journal, 1991
- Tight lower bounds for ShellsortJournal of Algorithms, 1990
- A lower bound on the size of shellsort networksPublished by Association for Computing Machinery (ACM) ,1989
- Practical variations of shellsortInformation Processing Letters, 1987
- A new upper bound for ShellsortJournal of Algorithms, 1986
- Improved upper bounds on shellsortJournal of Computer and System Sciences, 1985
- An efficient variation of bubble sortInformation Processing Letters, 1980
- An analysis of (h, k, 1)-ShellsortJournal of Algorithms, 1980
- An empirical study of minimal storage sortingCommunications of the ACM, 1963
- A high-speed sorting procedureCommunications of the ACM, 1959