Python 1.5.2 list sorting bug

[Tim Peters]

[Brian Kelley, finding a phantom bug, and then embracing a
 phantom solution <wink>]

> actually a much quicker test is:
>
> Python 1.5.2 (#1, Oct 27 1999, 17:21:07) [C] on irix646
> Copyright 1991-1995 Stichting Mathematisch Centrum, Amsterdam
> >>> a = [3,4,5,1,2]
> >>> a.sort(lambda x,y: x>y)
> >>> a
> [3, 4, 5, 1, 2]
> >>>

OK, everyone has beat you soundly about the head and shoulders for not using
a 3-outcome sort function -- and they were right to do so.  I should really
keep quiet at this point, but I can't resist:

>>> a = [3,4,5,1,2]
>>> a.sort(lambda x,y: -(x<y))
>>> a
[1, 2, 3, 4, 5]
>>> a.sort(lambda x,y: -(y<x))
>>> a
[5, 4, 3, 2, 1]
>>>

Those strange-looking comparison functions only return one of -1 or 0, yet
reliably get the job done despite that x>y didn't do a thing for you.
Here's an even stranger one:

>>> a
[5, 4, 3, 2, 1]
>>> a.sort(lambda x,y: x<y and -42 or 42)
>>> a
[1, 2, 3, 4, 5]
>>>

I will reveal the truth, but nobody is allowed to exploit it <0.9 wink>:
the sort in 1.5.2 has nothing in common with the sort in 1.5.1.  Most of the
rewrite aimed at speed and safety (in 1.5.1 and before it was possible to
crash Python by modifying the list *during* the sort), but part was in
anticipation of the long-awaited "rich comparison" changes expected in 1.6:
of each comparison outcome, the 1.5.2 list.sort() asks only "is it less than
0?".  It never asks whether it's equal to 0, or whether it's greater than 0.
So a two-outcome function *can* work fine, provided it correctly delivers
the one distinction list.sort() is now looking for.

BTW, this is so that a user class in 1.6 can get a decent sort even if
__lt__ is the only comparison function it defines.  Full-blown cmp isn't
needed to sort, so the algorithm was rewritten not to require full-blown
cmp.  In 1.5.2, though, you can't yet exploit that except via horrid
trickery like the above.

first-person-to-use-it-in-a-program-gets-shot-ly y'rs  - tim