Python 3 sorting: Custom comparer removed in favor of key - why?

Question

In Python 2.4, you can pass a custom comparer to sort.

Let's take the list -

list=[5,1,2,3,6,0,7,1,4]

To sort with the even numbers first, and then odds, we can do the following -

evenfirst=lambda x,y:1 if x%2>y%2 else -1 if y%2>x%2 else x-y
list.sort(cmp=evenfirst)
list == [0, 2, 4, 6, 1, 1, 3, 5, 7] # True

In Python 3, you can only pass key (which is also supported in Python 2.4).

Of course, the same sorting can be achieved in Python 3 with the right key:

list.sort(key=lambda x:[x%2,x])

---

I am curious about the decision of not supporting custom comparers anymore, especially when it seems something that could be implemented easily enough.

Is it true that in all, or most of the cases, a desired sort order has a natural key?

In the example above for example, such a key exists - and actually the code becomes more succinct using it. Is it always the case?

(I am aware of this recipe for converting comparer to key, but ideally, one should not have to take such workarounds if it could be built into the language.)

Answer 1

Performance.

The cmp function was called every time the sorting algorithm needed a comparison between two elements.

In contrast, the key object can be cached. That is, the sorting algorithm only needs to get the key once for each element and then compare the keys. It doesn't need to get a new key for every comparison.

Answer 2

Sorting by keys is well-defined, meaning the result doesn't depend on which (stable) sorting algorithm you use. There's no pathological key function. You might suggest random.random(), but that simply shuffles the list.

Whereas sorting with a compare function is well-defined only if the function is transitive and antisymmetric, which Python can neither test nor prove. What happens if you sort by nonsense compare function lambda(x, y): 1? You can't say, the result depends on the algorithm. Some algorithms might not even terminate.