Improved upper bounds on shellsort

摘要

The running time of Shellsort, with the number of passes restricted to O(log N), was thought for some time to be Θ(N32), due to general results of Pratt. Sedgewick recently gave an O(N43) 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 + ε√1g N) for any ε0.