[Tim]
A larger lesson: even if Python gets a stable sort and advertises stability (we don't have to guarantee it even if it's there)
[/F]
if we guarantee it, all python implementors must provide one.
Or a middle ground, akin to CPython's semi-reluctant guarantees of refcount semantics for "timely" finalization. A great many CPython users appear quite happy to rely on this despite that the language doesn't guarantee it.
how hard is it to implement a reasonably good stable sort from scratch?
A straightforward mergesort using a temp vector of size N is dead easy, and reasonably good (O(N log N) worst case). There aren't any other major N log N sorts that are naturally stable, nor even any I know of (and I know of a lot <wink>) that can be made stable without materializing list indices (or a moral equivalent). Insertion sort is naturally stable, but is O(N**2) expected case, so is DOA.
I can think of lots of really stupid ways to do it on top of existing sort code, which might be a reason to provide two different sort methods: sort (fast) and stablesort (guaranteed, but maybe not as fast as sort). in CPython, both names can map to timsort.
I don't want to see two sort methods on the list object, for reasons explained before. You've always been able to *get* a stable sort in Python via materializing the list indices in a 2-tuple, as in Alex's "stable sort" DSU recipe: http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/52234 People overly <wink> concerned about portability can stick to that.
(shouldn't you be writing a paper on this, btw?
I don't think there's anything truly new here, although the combination of gimmicks may be unique. timsort.txt is close enough to a paper anyway, but better in that it only tells you useful things; the McIlroy paper covers all the rest <wink>.
or start a sort blog ;-)
That must be some sort of web thing, hence beyond my limited abilities.