What does sorted()'s key argument receive, and how many times is it called?

## The contract `key` is any callable of **one argument**. Python calls it on each element and remembers the result; the sort then compares those results, never the elements themselves. When `key` is `None` (the default) the elements are compared directly. This applies identically to `sorted()`, `list.sort()`, `min()`, `max()`, `heapq.nlargest()` and `heapq.nsmallest()` — `key=` is a language-wide convention, not a quirk of one function. ## Exactly n calls The single most-tested fact here: the key function runs **once per element**, before any comparison. CPython builds a parallel array of computed keys and sorts by it, then reassembles the elements — the classic "decorate, sort, undecorate" pattern, done for you in C. So on a list of 100,000 records, a key that parses a timestamp runs 100,000 times, not the ~1.7 million times a pairwise comparator would. This is the whole reason Python 3 dropped comparator functions in favour of key functions: it converts a per-comparison cost into a per-element cost. A consequence people miss: the key is computed even for elements that end up needing few comparisons, and the computed keys are held in memory for the duration of the sort. A key that returns a large object multiplies memory; a key that returns a small tuple of primitives is cheap. ## Tuple keys and multi-field ordering Tuples compare lexicographically: the first components decide, and later components are only consulted on a tie. That gives multi-field ordering for free. ```python rows.sort(key=lambda r: (r["dept"], r["name"])) ``` Mixing directions is the interesting case, because `reverse=` applies to the whole ordering, not to one field. Two idioms cover it. For numbers, negate the field you want descending: `key=lambda r: (r["dept"], -r["score"])`. For values you cannot negate — strings, dates — sort twice, **least significant field first**, and let stability preserve the earlier work: sort by name ascending, then sort by score descending; equal scores keep the name order established by the first pass. One more subtlety about `reverse=True`: it flips the overall order but the sort **remains stable**. Elements with equal keys keep their original relative order rather than appearing reversed. That is a deliberate guarantee, and it is what makes the two-pass idiom above work. ## operator.itemgetter and operator.attrgetter `operator.itemgetter(1)` returns a callable equivalent to `lambda r: r[1]`, and `operator.attrgetter("created")` to `lambda o: o.created`. Both are implemented in C, so they avoid a Python-level function call per element — worth a real percentage on large sorts, and arguably more readable. Both accept several arguments and then return a tuple, which composes perfectly with tuple ordering: ```python from operator import itemgetter, attrgetter rows.sort(key=itemgetter("dept", "name")) objs.sort(key=attrgetter("dept", "name")) ``` `attrgetter` also understands dotted paths (`attrgetter("owner.name")`), and `operator.methodcaller("strip")` covers the "call a method on each element" case. ## Keys must be mutually comparable Python 3 removed default ordering between unrelated types, so a key that returns `int` for some rows and `str` for others raises `TypeError: '<' not supported between instances of 'str' and 'int'` — and only *sometimes*, because the failure depends on whether two mismatched keys are ever compared. A key returning `None` for missing data is the usual culprit. The fix is a **total** key that normalizes the gap, for example `key=lambda r: (r.get("score") is None, r.get("score", 0))`, which sorts the missing values to one end using a boolean as the leading component. ## Common key functions `key=len`, `key=abs`, `key=str.lower` (or `str.casefold` for case-insensitive text beyond ASCII), `key=os.path.getmtime`, and unbound methods passed as functions are all idiomatic — note `str.lower`, not `str.lower()`, since the callable itself is wanted, not the result of calling it. Passing a called expression is the second most common mistake after forgetting that `key` is keyword-only: `sorted(words, len)` raises `TypeError` because `sorted` takes exactly one positional argument. ## In review When you see a sort in a code review, three questions cover almost everything: is the key doing work that should be precomputed once outside the sort, is it total (no mixed types, no `None` holes), and does a tuple key say the multi-field intent more clearly than a chain of separate sorts? A well-chosen key turns an ordering rule into a single readable expression.