[Python-Dev] RE: companies data for sorting comparisons

[Tim Peters]

[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.