sort by last then by first

[Alex Martelli]

Jørgen Cederberg wrote:
   ...
> When sorting a list by several fields, I use this method:
> 
>  >>> names=[['Flintstone', 'Fred'],['Flintstone', 'Wilma'],['Rubble',
> ... 'Barney'],['Rubble', 'Betty'],['Flintstone', 'Pebbles']]
>  >>> snames = [ (x[1], x[0], x) for x in names]
>  >>> snames.sort()
>  >>> sortednames = [x[-1] for x in snames]
>  >>> sortednames
> [['Rubble', 'Barney'], ['Rubble', 'Betty'], ['Flintstone', 'Fred'],
> ['Flintstone
> ', 'Pebbles'], ['Flintstone', 'Wilma']]
>  >>>
> 
> I create a list of tuples, where the tuple is ordered in the way I want
> to sort, i.e. "sort by last then by first". The last element is the
> original item to be sorted. Sort them, and then extract the original item.
> 
> Maybe there are faster and easier ways, but I understand this one.

There is no substantially faster way than this approach (the "Decorate,
Sort, Undecorate" idiom, aka DSU) for long-enough lists.  There _are_
several slight variants that can come in handy sometimes, e.g. inserting 
in each item of sortednames the index into names of the corresponding
item, in order to make the sort "stable" (items that compare equal on
all compared fields are then guaranteed to stay in the same order as
they were originally -- the sort method, per se, is not stable up to
Python 2.2, and is not guaranteed to remain stable in the future even
though it is in 2.3).

I entirely agree that, almost always, DSU is simpler as well as faster
(when it counts, i.e., for large lists) than the alternatives.  The
main exceptions come when the sort needs to be ascending on certain
fields but descending on others -- _then_ DSU gets a bit hairier.


Alex