In which versions is list.sort stable?

[Tim Peters]

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

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.

stability-is-the-answer-to-fewer-questions-than-are-asked-ly y'rs  - tim