Large Dictionaries

Marcin Ciura Marcin.Ciura at
Fri Jun 9 12:16:03 CEST 2006

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

More information about the Python-list mailing list