sorting on keys in a list of dicts

Nick Coghlan ncoghlan at iinet.net.au
Fri Jan 7 18:17:23 CET 2005

```It's me wrote:
> What does it mean by "stability in sorting"?
>
> Can somebody please give a sample for using the code posted?  I am a little
> lost here and I like to know more about the use of keys....

It's the jargon for what Jeff said - if you are sorting by some value calculated
from each list entry, and different list entries may give the same value, then a
stable sort guarantees that the order of entries giving the same value will be
preserved from the original list.

Consider:

Py> from operator import itemgetter as item
Py> seq = [(1, 1), (2, 1), (2, 3), (1, 5)]
Py> seq.sort(key=item(1))
Py> seq #1
[(1, 1), (2, 1), (2, 3), (1, 5)]
Py> seq.sort(reverse=True)
Py> seq #2
[(2, 3), (2, 1), (1, 5), (1, 1)]
Py> seq.sort(key=item(1))
Py> seq #3
[(2, 1), (1, 1), (2, 3), (1, 5)]

This snippet sorts the tuples according to the second item, then sorts them in
reverse order of the whole tuple, then resorts them according to the second item.

Notice that the order of the first two items is different between point #1 and
point #3. This is because sorting by the second item makes no distinction
between these two tuples, and they retain whatever order they had before the
sort began.

This is what it means to have a stable sort, and it makes expressing complex
sorting quite easy by chaining different sort operations together.

Python 2.3 has a stable sort, and Python 2.4 brought the guarantee that it shall
remain that way. I'm not sure about Python 2.2 and earlier.

Cheers,
Nick.

--
Nick Coghlan   |   ncoghlan at email.com   |   Brisbane, Australia
---------------------------------------------------------------
http://boredomandlaziness.skystorm.net

```