A lower bound on the size of shellsort networks
- 1 March 1989
- proceedings article
- Published by Association for Computing Machinery (ACM)
Abstract
The central result of this paper is that all Shellsort sorting networks based on monotonically decreasing increments require ~t(N log 2 N/log log N) comparators. This result is significant because previously only the trivial fl(N log N) bound was known for this class of networks. Thus this paper provides the first proof that such networks cannot be of optimal size. The lower bound obtained in this paper nearly matches the upper bound of O(N log 2 N) that was proven by Pratt.Keywords
This publication has 8 references indexed in Scilit:
- A new upper bound for ShellsortJournal of Algorithms, 1986
- Improved upper bounds on shellsortJournal of Computer and System Sciences, 1985
- Tight Bounds on the Complexity of Parallel SortingIEEE Transactions on Computers, 1985
- An 0(n log n) sorting networkPublished by Association for Computing Machinery (ACM) ,1983
- An efficient variation of bubble sortInformation Processing Letters, 1980
- An empirical study of minimal storage sortingCommunications of the ACM, 1963
- A high-speed sorting procedureCommunications of the ACM, 1960
- A high-speed sorting procedureCommunications of the ACM, 1959