How many times does sorted() call the key= function, and why does it matter?

### The answer: exactly once per element For `sorted(iterable, key=f)`, `f` is called **n times for n elements** — once each — and never again. It is not called on every comparison. That single fact is what makes `key=` safe to use with work that would be unthinkable inside a comparator. ```python calls = 0 def sort_key(value): global calls calls += 1 return value % 10 sorted(range(1000), key=sort_key) print(calls) # 1000 ``` ### Why: decorate-sort-undecorate is built in CPython implements this with the pattern that used to be written by hand (the "decorate, sort, undecorate" idiom). The implementation: 1. walks the input once, calling the key callable on each element and storing the results in an internal array of keys alongside the array of values; 2. sorts the **keys** array, applying every move to the values array in lockstep; 3. throws the keys array away and returns the reordered values. Two consequences follow. First, all keys are computed *before* any comparison happens, so an exception raised by the key surfaces before the ordering work starts. Second, the comparisons performed during the sort are comparisons **between key objects**, via their `__lt__` — the original elements are never compared at all once keys exist. ### The cost model Say a geocoding batch produces 200,000 candidate address records, and the sort key normalizes each address into a canonical string — strip punctuation, casefold, collapse whitespace. With `key=`: * **200,000** key evaluations, i.e. O(n); * roughly **n log n** comparisons, but of the cheap normalized strings. If the same normalization ran inside a two-argument comparator, it would run on *both operands of every comparison* — on the order of 3.5 million times for the same batch, seventeen times the work, for an identical result. That ratio is the whole point of the parameter, and it is why "just put the expensive transform in the key" is correct advice rather than a hack. `min()` and `max()` are the same story in one pass: n key calls and n-1 comparisons, no sort. `heapq.nsmallest()` and `heapq.nlargest()` also evaluate their key once per element. ### What this means in practice **Do not hand-roll caching.** Wrapping the key in a memoizing decorator for a single `sorted()` call buys nothing — each element is keyed exactly once, so every lookup is a miss plus the cost of hashing the argument. Caching only pays when the *same* elements are sorted repeatedly across calls, or when many distinct elements share a key value and the key is genuinely expensive. **Do not hand-roll the decoration either.** Building `[(f(x), x) for x in data]`, sorting that, and stripping the pairs reproduces exactly what `sorted()` already does, adds n tuple allocations, and introduces a bug the builtin does not have: if two keys tie, the tuple comparison falls through to comparing the *elements*, which may raise `TypeError` for objects with no ordering. Write the decoration yourself only when you actually need the key values afterwards. **Do watch memory.** The keys array holds n references, and the key objects themselves are live for the duration of the sort. A key that returns a large normalized string or a long tuple for every one of several million rows is a real allocation spike on top of the input. **Do watch comparison cost, not just key cost.** The n key calls are linear; the comparisons are not. A cheap key that returns a 40-element tuple, or a very long string that shares a long common prefix with its neighbours, moves the expense into the O(n log n) half where it hurts far more. The sharpest version of this answer names both halves: keys are computed n times, compared about n log n times, so make the key *cheap to compute and cheap to compare*. **Do keep the key pure.** Because keys are all computed up front, a key whose result depends on mutable state that the sort itself changes cannot possibly do what its author intended — the ordering is decided from a snapshot taken before any element moves.