Improved upper bounds on shellsort
- 1 November 1983
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 02725428,p. 48-55
- https://doi.org/10.1109/sfcs.1983.26
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