Large Dictionaries

[Marcin Ciura]

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
   Marcin