
[Andrew Koenig]
Yes, I know that -1 is a valid truth value.
So the first time you care is the first time f(x, y) returns nonzero. Now you can find out what kind of function f is by calling f(y, x). If f(y, x) returns zero, f is <. Otherwise, it's a 3-way comparison.
[Greg Ewing]
I think the worry is that the function might be saying "true" to both of these, but just happen to spell it 1 the first time and -1 the second.
Then it's answering true to both x < y ? and y < x ? The comparison function is insane, then, so it doesn't matter what list.sort() does in that case (the algorithm is robust against insane comparison functions now, but doesn't define what will happen then beyond that the output list will contain a permutation of its input state). I've ignored this scheme for two reasons: anti-Pythonicity (having Python guess which kind of comparison function you wrote is anti-Pythonic on the face of it), and inefficiency. list.sort() is so bloody highly tuned now that adding even one test-&-branch per comparison, in C, on native C ints, gives a measurable slowdown, even when the user passes an expensive comparison function. In the case that no comparison function is passed, we're able to skip a layer of function call now by calling PyObject_RichCompareBool(X, Y, Py_LT) directly (no cmp-to-LT conversion is needed then). Against that, it could be natural to play Andrew's trick only in count_run() (the part of the code that identifies natural runs). That would be confined to 2 textual comparison sites, and does no more than len(list)-1 comparisons total now.