Sorting list (maybe stupid)

[Tim Peters]

[Delaney, Timothy]
> ...
> Personally, I think the implementation should be documented to
> use a stable sort - presumably mergesort (stable, minimal number of
> comparisons which is very important in Python).

Write a mergesort as fast and memory-efficient as the sort we've got and
we'll consider it.  I wasn't able to.  Great progress in memory-efficient
mergesort algorithms has been made over the last decade (the ancient one
<wink> in a Knuth Vol 3 exercise achieves memory efficiency at the cost of
vastly more comparisons), but I don't know whether they're truly practical
yet.  Count the # of comparisons the samplesort/binary_insertion hybrid
actually does and you'll find that mergesort doesn't have enough of an
advantage there to make up for the speed it loses due to greater data
movement.