[Python-Dev] decorate-sort-undecorate

[Guido van Rossum]

> What about the situation where you want the list sorted in reverse order? 
> If you simply sort and then reverse the list you've broken the stability. 

Yes, that's the same thing Alex Martelli brought up.  You could also
supply a cmp function, as Geoffrey Talvola suggested (though this will
make the comparisons more costly).

> You *could* preserve the stability by using a negative index when the list 
> is to be reserved, but might it also be possible to get the special 
> comparison object to invert the result of the comparison?

That's a possibility.  Since we've got a reverse keyword argument,
that could be implemented.  (There would have to be two classes, one
with a forward comparison and one with a reverse, to get this info
efficiently into the wrapper objects without using globals.)

But then I wonder what should happen if you specify reverse without
key.  The obvious way to implement this is to do the stable sort
without wrappers and then reverse the whole list, but this also breaks
stability (as you define it).  So maybe specifying reverse should
force using wrappers?  But that's unintuitive in a different way: if
you don't care about the stability of the sort (e.g. if equal keys are
impossible or unlikely), you'd expect the reverse option to simply
reverse the list after sorting it, and using wrappers would make it a
lot slower than that.

How important do you think this is?  We could punt on the issue,
implement reverse by reverting the list afterwards.  (I could define
stability differently and be totally happy with getting everything in
reverse order rather than only the specified key. :-)

--Guido van Rossum (home page: http://www.python.org/~guido/)