In which versions is list.sort stable?

Brian Quinlan brian at sweetapp.com
Tue Apr 29 02:56:05 CEST 2003


Cheers,
Brian 

> -----Original Message-----
> From: python-list-admin at python.org
[mailto:python-list-admin at python.org]
> On Behalf Of Frantisek Fuka
> Sent: Monday, April 28, 2003 17:15
> To: python-list at python.org
> Subject: Re: In which versions is list.sort stable?
> 
> Can you please explain to a newbie what this thread means?

A stable sort is a sorting algorithm that does not change the relative
order of elements that have equal values. It has nothing to do with
crashing. Here is an example:

Python 2.2.1 Build...
>>> stuff = [("grape", 5.50), ("banana", 5.50), ("cherry", 3)]
>>> stuff.sort(lambda x,y: cmp(x[1], y[1]))
>>> print stuff
[('cherry', 3), ('banana', 5.5), ('grape', 5.5)]

As you can see, the banana and grape tuples have been swapped even
though swapping them was not necessary to satisfy the sorting condition.
So the Python 2.2 sorting algorithm is not stable. The Python 2.3
sorting algorithm is i.e. if would return:
[('cherry', 3), ('grape', 5.5), ('banana', 5.5)]

Cheers,
Brian






More information about the Python-list mailing list