Guido rethinking removal of cmp from sort method

[Dan Stromberg]

On Mon, Mar 28, 2011 at 6:58 PM, Paul Rubin <no.email at nospam.invalid> wrote:

> DSU is a clever and useful design pattern, but comparison
> sorting is what all the sorting textbooks are written about.
>

Actually, even though I wrote one program that could almost benefit from cmp
sorting that might have trouble with key sorting, I think it was probably
the right decision to remove cmp sorting.  I say "almost", because I've
since rewritten it with a specialized sort that gives it a much better
asymptotic runtime and better fault tolerance, so what Python 3 does out of
the box for sorting won't matter to it much.

I say "it's probably the right decision", because it's almost always going
to be faster to use a key sort, at least in CPython <= 3.2, and it's almost
never less functional to use a key sort.  Using a key sort also opens the
door to a radixsort, not that radixsort is really that interesting as sorts
go (It's still pretty much O(nlogn), statements to the contrary
notwithstanding), but it's nice to know that the possibility is there.

If you run across one of the infrequent, specialized sorting needs that
require a cmp sort, there's not really anything wrong with using cmp_to_key
or including your own sort routine.  I put a bunch of Python sorts at
http://stromberg.dnsalias.org/cgi-bin/viewvc.cgi/sorts/compare/trunk/?root=svn-
but I've not  needed to add cmp -or- key comparisons to them yet - so
far
they just use <, >, ==, etc.

The program I mentioned above doesn't use any of these - it has its own,
relatively unique sort algorithm - mostly to collapse same-valued elements
into a list to avoid re-compares, and to eliminate elements that give errors
during the sort.

I leave off with this: Python -must- resist the temptation to become all
things to all people, because no language can ever truly -be- all things to
all people.  I much prefer having a nice small core language to having a
kitchen sink language.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/python-list/attachments/20110328/c1e0ab11/attachment-0001.html>