[Tim Peters] >> ... >> O(N log N) sorting algorithms helped by pre-existing order are >> uncommon, unless they do extra work to detect and exploit >> pre-existing order.
[Lawrence D'Oliveiro] > Shellsort works well with nearly-sorted data. It's basically a smarter > version of bubblesort with much improved efficiency. It's also very > compact to implement. shellsort is much more a refinement of insertion-sort than of bubblesort, but is not an O(N log N) algorithm regardlesss. A nice, succinct summary of what was known about shellsort's behavior as of Sedgewick's 1996 "Analysis of Shellsort and Related Algorithms" can be found here: http://www.inf.fh-flensburg.de/lang/algorithmen/sortieren/shell/shellen.htm -- http://mail.python.org/mailman/listinfo/python-list