Large Dictionaries

[Lawrence D'Oliveiro]

In article <mailman.6554.1149519174.27775.python-list at python.org>,
 "Tim Peters" <tim.peters at gmail.com> wrote:

>For example, the O(N log N) heapsort is unreasonable compared to the
>O(N**2) bubblesort by that reasoning (pre-sorted is actually a bad
>case for heapsort, but a good case for bubblesort)?  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.

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.