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 -- http://mail.python.org/mailman/listinfo/python-list
