How does the functools cmp_to_key function work?

In Python, both list.sort method and sorted built-in function accepts an optional parameter named key, which is a function that, given an element from the list returns its sorting key.

Older Python versions used a different approach using the cmp parameter instead, which is a function that, given two elements from the list returns a negative number if the first is less than the second, zero if there are equals and a positive number if the first is greater. At some point, this parameter was deprecated and wasn’t included in Python 3.

The other day I wanted to sort a list of elements in a way that a cmp function was much more easier to write than a key one. I didn’t wanted to use a deprecated feature so I read the documentation and I found that there is a funtion named cmp_to_key in the functools module which, as his name states, receives a cmp function and returns a key one… or that’s what I thought until I read the source code (or at least an equivalent version) of this high level function included in the docs

def cmp_to_key(mycmp):
    'Convert a cmp= function into a key= function'
    class K(object):
        def __init__(self, obj, *args):
            self.obj = obj
        def __lt__(self, other):
            return mycmp(self.obj, other.obj) < 0
        def __gt__(self, other):
            return mycmp(self.obj, other.obj) > 0
        def __eq__(self, other):
            return mycmp(self.obj, other.obj) == 0
        def __le__(self, other):
            return mycmp(self.obj, other.obj) <= 0
        def __ge__(self, other):
            return mycmp(self.obj, other.obj) >= 0
        def __ne__(self, other):
            return mycmp(self.obj, other.obj) != 0
    return K

Despite the fact that cmp_to_key works as expected, I get surprised by the fact that this function doesn’t return a function but a K class instead. Why? How does it work? My guess it that the sorted function internally checks whether cmp is a function or a K class or something similar, but I’m not sure.

P.S.: Despite this weirdness, I found that K class is very useful. Check this code:

from functools import cmp_to_key

def my_cmp(a, b):
    # some sorting comparison which is hard to express using a key function

class MyClass(cmp_to_key(my_cmp)):
    ...

This way, any list of instances of MyClass can be, by default, sorted by the criteria defined in my_cmp

Answer

No, sorted function (or list.sort) internally does not need to check if the object it received is a function or a class . All it cares about is that the object it received in key argument should be callable and should return a value that can be compared to other values when called.

Classes are also callable , when you call a class , you receive the instance of that class back.

To answer your question, first we need to understand (atleast at a basic level) how key argument works –

1. The key callable is called for each element and it receives back the object with which it should sort.

2. After receiving the new object, it compares this to other objects (again received by calling the key callable with the othe element).

Now the important thing to note here is that the new object received is compared against other same objects.

Now onto your equivalent code, when you create an instance of that class, it can be compared to other instances of the same class using your mycmp function. And sort when sorting the values compares these objects (in-effect) calling your mycmp() function to determine whether the value is less than or greater than the other object.

Example with print statements –

>>> def cmp_to_key(mycmp):
...     'Convert a cmp= function into a key= function'
...     class K(object):
...         def __init__(self, obj, *args):
...             print('obj created with ',obj)
...             self.obj = obj
...         def __lt__(self, other):
...             print('comparing less than ',self.obj)
...             return mycmp(self.obj, other.obj) < 0
...         def __gt__(self, other):
...             print('comparing greter than ',self.obj)
...             return mycmp(self.obj, other.obj) > 0
...         def __eq__(self, other):
...             print('comparing equal to ',self.obj)
...             return mycmp(self.obj, other.obj) == 0
...         def __le__(self, other):
...             print('comparing less than equal ',self.obj)
...             return mycmp(self.obj, other.obj) <= 0
...         def __ge__(self, other):
...             print('comparing greater than equal',self.obj)
...             return mycmp(self.obj, other.obj) >= 0
...         def __ne__(self, other):
...             print('comparing not equal ',self.obj)
...             return mycmp(self.obj, other.obj) != 0
...     return K
...
>>> def mycmp(a, b):
...     print("In Mycmp for", a, ' ', b)
...     if a < b:
...         return -1
...     elif a > b:
...         return 1
...     return 0
...
>>> print(sorted([3,4,2,5],key=cmp_to_key(mycmp)))
obj created with  3
obj created with  4
obj created with  2
obj created with  5
comparing less than  4
In Mycmp for 4   3
comparing less than  2
In Mycmp for 2   4
comparing less than  2
In Mycmp for 2   4
comparing less than  2
In Mycmp for 2   3
comparing less than  5
In Mycmp for 5   3
comparing less than  5
In Mycmp for 5   4
[2, 3, 4, 5]