In which versions is list.sort stable?

[Beni Cherniavsky]

Tim Peters wrote on 2003-04-27:

> [Beni Cherniavsky]
> > Why don't we just grow a `list.stablesort` method that can be an alias
> > to `list.sort` currently but is guaranteed to be some stable sort
> > forever?  Explicit is better than implicit, so in the rare case that
> > you do rely on it, why not spell it out?
>
> Because Guido has shown no interest in saying that Python-the-language
> guarantees to provide a stable sorting method.  Now that 2.3 has a stable
> sort, I expect many apps will find that it's still more efficient to force
> stability via injecting sequence indices into sort tuples.  That is,
>
>     temp = [(obj.key(), i, obj) for i, obj in enumerate(list_of_objects)]
>     temp.sort()
>     result = [obj for key, i, obj in temp]
>
Neat trick, never occurred to me to force stability with the
{,un}decorate pattern (although I'm well familiar with it), perhaps
because I never needed a stable sort so far <wink>.  I made this
suggestion simply because I thought of this as a cleaner way
immediately after I saw the announcement that "it's now stable but
without promises"...

> will often be faster than
>
>     temp = [(obj.key(), obj) for obj in list_of_objects]
>     temp.sort()
>     result = [obj for key, obj in temp]
>
> The hangup is that tuple comparison breaks ties in the first element
> position by going on to compare more element positions.  In the latter
> spelling, that can invoke arbitrarily expensive object comparison, but in
> the former spelling is always resolved no latter than by comparison of
> unequal ints.
>
> This became painfully clear during timing tests run while the 2.3 sort was
> being developed, on a database-sorting example contributed by an alpha
> tester, where primary keys where often equal.  Forcing stability in that
> test ran twice as fast as when leaving the sequence indices out of the
> tuples.
>
Even more neat; I think I can use this trick right now.  Perhaps the
docs should mention this right after saying that "code that intends to
be portable across implementations and versions must not rely on
stability".  Hmm, this "perhaps the docs should say X" theme is
recurring lately.  I wander what would happen if the docs would be
turned into a Wiki (probably - a mess - but a pseudo-wiki that
automagically turns edits into submitted patches or something like
that could be convenient.

[s.split("-ly y'rs\n")[::-1] for s in signatures].sort()-ly y'rs
Beni Cherniavsky <cben at tx.technion.ac.il>