Large Dictionaries

Marcin Ciura Marcin.Ciura at NOSPAM.poczta.onet.pl
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
http://sun.iinf.polsl.gliwice.pl/~mciura/shellsort.pdf
   Marcin



More information about the Python-list mailing list