# [Tutor] Sorting Nested Lists

Steven D'Aprano steve at pearwood.info
Mon Jan 9 13:56:22 CET 2012

```Sarma Tangirala wrote:
> Hi list,
>
> I was banging my head about a pythonic way of doing the following,
>
> Given a nested list, how do I sort the uppermost list based on one key and
> when a special condition occurs a sort on another key should be performed?
> For example, [[1,2], [2, 2], [3, 2], [4, 0]] would be sorted, in my example
> as, [[4, 0], [3, 2], [2, 2], [1, 2]]. That is, sort on the second value and
> in case they are equal, reverse sort on the first value.

That is not exactly a good example. There are at least two other ways to get
the result you show, both much more obvious:

py> L = [[1,2], [2, 2], [3, 2], [4, 0]]
py> list(reversed(L))
[[4, 0], [3, 2], [2, 2], [1, 2]]
py> sorted(L, reverse=True)
[[4, 0], [3, 2], [2, 2], [1, 2]]

If I ignore your example, and just use the description:

"sort on the second value, and in case they are equal, reverse sort on the
first value"

the way to do this is with a double sort. Note that this works because
Python's sort is stable: in the event of ties, the first item remains first.
In earlier versions of Python, this was not always the case.

So, given this list:

L = [[1,2], [4,0], [3,2], [2,2], [5,1], [1,1]]

first sort in reverse by the first item, then by the second:

py> L.sort(key=lambda sublist: sublist[0], reverse=True)
py> L.sort(key=lambda sublist: sublist[1])
py> print L
[[4, 0], [5, 1], [1, 1], [3, 2], [2, 2], [1, 2]]

Note that using a key function is MUCH more efficient than a cmp function.
Comparison functions end up doing much more work, and hence are very much
slower, than a key function.

Also note that in recent versions of Python, you can do without the lambda
function and use the special "itemgetter" function:

py> from operator import itemgetter
py> L = [[1,2], [4,0], [3,2], [2,2], [5,1], [1,1]]
py> L.sort(key=itemgetter(0), reverse=True)
py> L.sort(key=itemgetter(1))
py> print L
[[4, 0], [5, 1], [1, 1], [3, 2], [2, 2], [1, 2]]

Last but not least, I will show how to do it using a custom cmp function. But
I recommend that you don't use this!

def my_cmp(list1, list2):
x = cmp(list1[1], list2[1])
if x == 0:  # a tie
x = cmp(list2[0], list1[0])  # swap the order for reverse sort
# or if you prefer, x = -cmp(list1[0], list2[0])
return x

sorted(L, my_cmp)

--
Steven
```

More information about the Tutor mailing list