In which versions is list.sort stable?

[Jeff Epler]

On Tue, Apr 29, 2003 at 02:15:12AM +0200, Frantisek Fuka wrote:
> Can you please explain to a newbie what this thread means?
> 
> Should I not use SORT in Python 2.2.2? Docs do not mention anything 
> about "unstability". Are there any other "bacis" functions (and SORT 
> seems pretty basic to me) that I should avoid???

It's not that list.sort is buggy in some versions of Python.

The "stability" of a sort refers to the result of a sort on a list where
there is not a total ordering.  For instance, consider the following list:
	[4, 3a, 2, 3b]
where 3a and 3b are equal to each other, but distinct.

One possible sorted version of that list is
	[2, 3b, 3a, 4]
but if your sort routine gives this result then it is not "stable", because
3a was before 3b in the input, but not in the output.  The "stable" output
is
	[2, 3a, 3b, 4]

In Python 2.3, the sort happens to have the property that it will always
give the *second* result, while in other versions either result may be
given.  Unless the sort is "stable", either result is acceptable.

A non-stable sort can be made stable by sorting on a tuple of (l[i], i)
because now there are no equal but distinct elements.  This is one use of
the decorate-sort-undecorate idiom.  A "sort stably" function was posted
elsewhere in this thread that (I think) achieves the result in this way.
As Tim (author of the new sort) also posted, this may be faster anyway(!).

Jeff