Improved upper bounds on shellsort
- 1 November 1983
- proceedings article
- Published by Institute of Electrical and Electronics Engineers (IEEE)
Abstract
The running time of Shellsort, with the number of passes restricted to O(log N), was thought for some time to be Θ(N3/2), due to general results of Pratt. Sedgewick recently gave an O(N4/3) bound, but extensions of his method to provide better bounds seem to require new results on a classical problem in number theory. In this paper, we use a different approach to achieve O(N1+4/√2lgN).Keywords
This publication has 4 references indexed in Scilit:
- A new upper bound for ShellsortJournal of Algorithms, 1986
- Sorting by distributive partitioningInformation Processing Letters, 1978
- A Linear Diophantine ProblemCanadian Journal of Mathematics, 1960
- A high-speed sorting procedureCommunications of the ACM, 1959