Article,
Empirical Study of the Expected Running Time of Shellsort
The Computer Journal, 34 (1): 88--91 (1991)
DOI: 10.1093/comjnl/34.1.88
Abstract
We present the results of a large empirical study of the running time of Shellsort. A previous study reported by Knuth for several increment sequences gave running times between Θ(N1.25) and Θ(NN1.28) or Θ(Nlog2N). but these forms are not very accurate especially for large permutations.Our results given a running time of Θ(N5/4) for all of the increment sequences suggested by Knuth and Θ(N7/6) for an increment sequence suggested by Sedgewick. Our fits are accurate to within 1% for 250 ≤N<100000 and about 0.1% for larger N. Much of the error in the fits appears to be related to the error in the measured data. These results are significant because they suggest that O(log N) increment sequences with Θ(Nk) worst-case running times have Θ(N(k+1)/2) average-case running times and that there is no increment sequence for which Shellsort is O(Nlog N), even on average.
