What is the best way to merge two lists?

[Tim Peters]

[John Hunter, explains stability in sorting]
> ...
> Incidentally, the efficiency of sort in the yet-to-be-released
> python2.3 is rumored to be substantially improved.

For random data, it seems platform-dependent which wins, with more platforms
seemingly giving the edge to the 2.3 sort due to cache effects.  Both
methods do very close to the theoretical minimum # of compares on randomly
ordered data, so there was no room for "deep" improvement on random data
(and I'm just talking about CPython there; Jython's sort was a variant of
CPython's much older quicksort, and Jython benefited a lot even on random
data when Finn Bock ported the new sort to Java).

Where the 2.3 sort kicks ass is in exploiting many more kinds of partial
pre-existing order.  Lots of real data *is* partially ordered already, and
the algorithm discovers that and adapts to it, saving mountains of
comparisons when possible.

BTW, the 2.3 sort is stable, although the language specification doesn't
guarantee that.