[Python-Dev] "What's New": stable sorting?

Tim Peters tim.peters at gmail.com
Sat Jul 24 05:17:51 CEST 2004

[Greg Ward]
> Just reading through "What's New in Python 2.4" and I spotted this:
> """
> The results of sorting are now guaranteed to be stable. This means that
> two entries with equal keys will be returned in the same order as they
> were input. For example, you can sort a list of people by name, and then
> sort the list by age, resulting in a list sorted by age where people
> with the same age are in name-sorted order.
> """
> I thought the Tim-bot fixed Python's list.sort() to be stable *aaaages*
> ago -- 1.6 or 2.0 rings a bell.  Not true?

CPython's list.sort() first *became* stable in all cases in 2.3.  But
the 2.3 docs didn't guarantee stability, CPython just happened to
provide stability.  What's new here in 2.4 is that the docs now
guarantee stability.  This constrains future implementations,
something we weren't comfortable doing until lots of experience with
the new sort strongly suggested that only a fool would even consider
the possibility that a different implementation of sorting may ever
exist <wink>.

More information about the Python-Dev mailing list