sort by last then by first

Delaney, Timothy tdelaney at avaya.com
Thu Jan 30 00:36:04 CET 2003


> From: Alex Martelli [mailto:aleax at aleax.it]
> 
> Peter Abel wrote:
>    ...
> > If you change the order of sorting from
> > low order key to high order key, I can't see
> > any reason, why this shouldn't work stable.
> 
> the list.sort method is NOT guaranteed to be stable.
> It generally LOOKS stable, for small enough lists,
> up to Python 2.2 -- and it has been changed to one
> that happens to be stable in 2.3 -- but it's never
> a good idea to rely on such things, which may well
> change from one version to another: list.sort at any
> time will be the fastest sort Tim Peters can think
> up, whether that's a stable one or not.

Just a further note on this ... a lot of people try sorting short lists with
pre-2.3 and conclude that the sort is stable experimentally.

There is a reason for this ... the old sort algorithm (a quicksort variant)
falls back to a different algorithm when partitions are small enough. This
other algorithm just happens to be stable ...

In any case, even with the 2.3 stable sort (which is very fast),
Decorate-Sort-Undecorate as per 

http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/52234

has been tested to still be much faster.

Tim Delaney





More information about the Python-list mailing list