Large Dictionaries

[Tim Peters]

[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