Sorted associative container in Python?

[Tim Peters]

[Terry Reedy]
> Its worth noting that the current list.sort() method (starting in
> 2.2.2, I believe) works well (by design) with nonrandom special cases
> such as a sorted list with new items appended.  Slightly simplified,
> it will scan the list, notice that the first part is properly sorted,
> sorted the added tail, and then merge.

The adaptive mergesort is new in 2.3, and does act as described.  The
earlier samplesort did in fact special-case forward-sorted *or*
reverse-sorted, followed by up to 15 scrambled elements, and such cases run
in linear time there too.  The adaptive mergesort naturally exploits many
kinds of partial ordering; under samplesort (just) a few were caught via
special-case hacks (nevertheless effective in real life!).