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