sort the list

[Duncan Booth]

Neil Hodgson wrote:

>> Since no-one mentioned it and its a favourite of mine, you can use the
>> decorate-sort-undecorate method, or "Schwartzian Transform"
> 
>     That is what the aforementioned key argument to sort is: a built-in 
> decorate-sort-undecorate.

And crucially it is a built-in DSU which gets it right more often than 
naive DSU implementations.

e.g. it is stable when you reverse the order:

>>> lst = [[4,1],[4,2],[9,3],[5,4],[2,5]]
>>> list(reversed([ x[-1] for x in sorted([ (x[0],x) for x in lst ]) ]))
[[9, 3], [5, 4], [4, 2], [4, 1], [2, 5]]
>>> l1 = list(lst)
>>> l1.sort(key=operator.itemgetter(0), reverse=True)
>>> l1
[[9, 3], [5, 4], [4, 1], [4, 2], [2, 5]]

and it gets incomparable objects right:

>>> lst = [4+1j, 4+2j, 9+3j, 5+4j, 2+5j]
>>> [ x[-1] for x in sorted([ (x.real,x) for x in lst ]) ]

Traceback (most recent call last):
  File "<pyshell#39>", line 1, in -toplevel-
    [ x[-1] for x in sorted([ (x.real,x) for x in lst ]) ]
TypeError: no ordering relation is defined for complex numbers
>>> l1 = list(lst)
>>> l1.sort(key=operator.attrgetter('real'))
>>> l1
[(2+5j), (4+1j), (4+2j), (5+4j), (9+3j)]
>>>