Improved upper bounds on Shellsort
From MaRDI portal
The running time of Shellsort, with the number of passes restricted to O(log N), was thought for some time to be \(\Theta (N^{3/2})\), due to general results of Pratt. Sedgewick recently gave an \(O(N^{4/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(N^{1+\epsilon /\sqrt{lg N}})\), for any \(\epsilon >0\).
Recommendations
Cites work
- A Linear Diophantine Problem
- A new upper bound for Shellsort
- scientific article; zbMATH DE number 3841211 (Why is no real title available?)
- scientific article; zbMATH DE number 3473265 (Why is no real title available?)
- On the linear diophantine problem of Frobenius.
- Sorting in Average Time o(\log \,n)
- Tight Bounds on the Complexity of Parallel Sorting
Cited in
(14)- Lattice translates of a polytope and the Frobenius problem
- An improved shellsort algorithm
- Shellsort with a constant number of increments
- On shellsort and the Frobenius problem
- Shellsort with three increments
- Tight lower bounds for Shellsort
- The Frobenius Problem and Its Generalizations
- A new upper bound for Shellsort
- scientific article; zbMATH DE number 1256658 (Why is no real title available?)
- On the average-case complexity of Shellsort
- Analysis of Shellsort and related algorithms
- Spin-the-bottle sort and annealing sort: oblivious sorting via round-robin random comparisons
- Stochastic analysis of Shell Sort
- More on shellsort increment sequences
This page was built for publication: Improved upper bounds on Shellsort
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1069307)
