Large Dictionaries

[Duncan Booth]

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
> http://sun.iinf.polsl.gliwice.pl/~mciura/shellsort.pdf

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.