Why does sorted() need functools.cmp_to_key to use a three-way comparator?

## Two different ways to describe an order There are two classic ways to tell a sort what "in order" means. A **comparator** takes two elements and reports their relation as a number: negative if the first should come first, zero if they tie, positive if the second should come first. This is how Python 2's `list.sort(cmp=...)` worked, and it is how C's `qsort` and many other languages' sorts still work. A **key function** takes one element and returns a proxy value; the sort then orders the proxies with the ordinary `<` operator. This is the "decorate–sort–undecorate" idea, and it is the only mechanism Python 3 offers: `sorted(iterable, *, key=None, reverse=False)` and `list.sort` have no `cmp` parameter at all — it was removed in Python 3.0. The removal was deliberate. A key is faster, because it is called exactly once per element and the n log n comparisons that follow are then comparisons between the key values, usually at C speed. It is also easier to get right: there is no way to write a key function that describes an inconsistent order, whereas comparators can and do violate transitivity. And most real orderings are naturally expressible as a key — `key=len`, `key=str.lower`, `key=operator.itemgetter("ts")`, or a tuple `key=lambda r: (r.region, r.signup)` for multi-field ordering. ## What cmp_to_key does Legacy code and ported algorithms still have comparators, so the standard library provides the adapter: ```python from functools import cmp_to_key sorted(words, key=cmp_to_key(my_comparator)) ``` `functools.cmp_to_key(func)` returns a **callable class**. Calling it on an element produces a small wrapper object that holds the element and defines the rich-comparison methods; each of those methods calls `func(self.obj, other.obj)` and compares the returned number against zero. The sort therefore does what it always does — evaluate `key(element)` once per element, then compare the resulting objects with `<` — and your two-argument comparator gets invoked from inside those comparisons. Because it is nothing more than a key function, it works everywhere a key is accepted: `sorted`, `list.sort`, `min`, `max`, `heapq.nlargest`, `heapq.nsmallest`, and `itertools.groupby`. ## The three-way idiom Writing a comparator in Python, the compact way to produce −1/0/1 without branching is: ```python def cmp(a, b): return (a > b) - (a < b) ``` Booleans are integers, so this evaluates to 1, 0 or −1. Note the return value need only have the right **sign** — any negative or positive number works, which is why `len(a) - len(b)` is a valid comparator body for ordering by length. ## What it costs This is the part interviewers probe. A key function is called **n** times. A comparator is called once per comparison, which for Python's sort is on the order of **n log n** times, and every one of those calls is a Python-level function call plus an attribute lookup on a wrapper object. On top of that, wrapping allocates one object per element. The documentation says as much: `cmp_to_key` is provided for transition and for orderings a key cannot express, not as an equal alternative. On a large list the difference is routinely several-fold. So the decision rule is: **write a key if you can, and reach for `cmp_to_key` only when you cannot.** Cases where you genuinely cannot are narrower than people think, but they exist: * A comparator ported wholesale from another language or from Python 2, where re-deriving the ordering rule is riskier than adapting it. * An ordering that depends on the **pair** rather than on either element alone — for example a rule that says "if these two entries share a prefix, the shorter wins, otherwise compare case-insensitively" — where no single proxy value per element reproduces the relation. * Orderings computed by an external rule engine that only exposes "compare these two". Things people wrongly think need a comparator: multi-field ordering (use a tuple key), descending order (use `reverse=True`, or negate a numeric key), and descending on one field with ascending on another (sort twice, least-significant field first — Python's sort is stable, so earlier orderings survive within ties). ## Stability and reverse `cmp_to_key` does not change either of the sort's guarantees. The sort remains stable: elements the comparator reports as tied — a zero return — keep their relative input order. And `reverse=True` still reverses the ordering while preserving stability, rather than simply reversing the output list. That means a comparator that returns zero too eagerly does not scramble anything by itself; it just leaves those elements in whatever order the input happened to have.