What does functools.cmp_to_key do, and why is it slower than a plain key function?

## Why Python 3 has no comparison-function parameter Python 2's sort accepted a two-argument comparison function returning a negative number, zero or a positive number. Python 3 dropped it — both from the sort API and from the data model, where the single three-way comparison hook was replaced by the five rich comparison methods. The reason is cost and clarity. A comparator must be called for every comparison the sort performs, on the order of n log n Python-level calls; a key function is called once per element, n calls, and the comparisons then happen in C between the computed values. For a million elements that is roughly twenty million calls against one million. The rich comparison methods also express more than a three-way answer can. They allow one operand to decline (returning `NotImplemented`) so the other can answer, they allow partial orders where two values are simply not comparable, and they let `==` and `<` be defined independently. ## What `functools.cmp_to_key` does `functools.cmp_to_key(func)` takes a two-argument comparator and returns a callable suitable for `key=`. Calling it on an element produces a small wrapper object that stores the element and implements `__lt__`, `__le__`, `__gt__`, `__ge__` and `__eq__` — each one calling `func(self.obj, other.obj)` and comparing the returned number against zero. The sort therefore sorts wrappers, and every comparison between wrappers reaches back into your Python function. ```python import functools def by_stage(a, b): order = {"parse": 0, "enrich": 1, "index": 2} return order[a] - order[b] print(sorted(["index", "parse", "enrich"], key=functools.cmp_to_key(by_stage))) ``` It works with anything that takes `key=` — `sorted()`, `list.sort()`, `min()`, `max()`, `heapq.nsmallest()`. ## When to reach for it **Porting.** Old code, or code translated from a language whose sort APIs are comparator-based, arrives with the comparator already written and tested. Wrapping it is a one-line change that preserves behaviour exactly; rewriting the rule as a key is a separate, riskier commit. **Genuinely relational orders.** Some rules compare a *pair* and cannot be reduced to one value per element. Ordering strings so that concatenating them yields the largest possible number, or applying a table of pairwise precedence rules, are of this kind. There, a comparator is the honest expression of the rule and `cmp_to_key` is the right tool. **Everything else wants a key.** If the rule is “by this field, then that one, descending”, a tuple key is shorter, faster and easier to read. The example above is a comparator only for illustration — it should really be `key=order.__getitem__`, a lookup done once per element. ## The cost, concretely Both forms sort in the same asymptotic time; the constant differs sharply. The comparator pays a Python function call per comparison, plus the wrapper's own method dispatch, plus an attribute lookup on each side. In a batch job that sorts a large slice of a dataset on a cold start, this is the difference between a sort you never notice and one that visibly dominates a startup measured in tens of seconds. If a profile points at a comparator, the first thing to try is expressing the rule as a key — which is usually possible, and usually reveals that the comparator was doing something simpler than it looked. One related pitfall: the comparator must return a **number**, not a bool. `return a > b` returns `True` or `False`, and since `True` is 1 and `False` is 0, the “less than” case and the “equal” case become indistinguishable and the sort produces a wrong order without any error. Return the sign of a difference, or `-1`/`0`/`1` explicitly.