duncan.booth at invalid.invalid
Fri Jun 9 13:35:48 CEST 2006
Marcin Ciura wrote:
> Tim Peters wrote:
>> shellsort is much more a refinement of insertion-sort than of
>> bubblesort, but is not an O(N log N) algorithm regardlesss.
> With a judiciously chosen increment sequence,
> the number of comparisons made by shellsort
> *is* of the order N log N for practical values of N.
> See Figure 8 in
That isn't what the reference says. It only covers N up to a few thousand.
Practical values of N need to at least go up into the millions.
Read the summary:
> Using sequential analysis, the search for optimal increment sequences
> for Shellsort was accelerated enough to find them for arrays up to
> several thousand elements.
> However, the sequences obtained so far are too short to draw a
> reliable conclusion whether an appropriate sequence of increments can
> make Shellsort a O(N logN) sorting method on the average. Some
> hypotheses may be possible when the sequences are prolonged to sort
> arrays of about 10^5 elements.
More information about the Python-list