Order as a key

Sorting is rarely the answer to a problem. Sorting by the right key usually is, and the key is the part you have to invent — the sort itself is one line somebody else already wrote and tested.

So the question is never "which sort", it is "what is the order, stated as a function of one element". Most of the difficulty in this module is that question, and the rest of it is knowing what the library promises you when two elements answer it identically.

A key is computed once; a comparator runs on every comparison

Python's sort takes key, not a comparator, and the reason is arithmetic. key is called exactly once per element — n calls — and the resulting values are then compared at C speed. A comparator, which you reach through functools.cmp_to_key, is called once per comparison, which is about n log₂ n times, and every one of those is an interpreted function call.

At n = 10⁶ that is 10⁶ key calls against roughly 10⁶ × 20 = 2 × 10⁷ comparator calls. A factor of 20 in call count, before you account for a Python call being far more expensive than a tuple comparison in C.

rows.sort(key=lambda r: (r.dept, -r.salary))    # 10**6 key calls

from functools import cmp_to_key
rows.sort(key=cmp_to_key(compare))              # ~2 * 10**7 calls into compare

Reach for a comparator only when the order genuinely cannot be written as a value per element. That is rarer than it looks: most orders that feel like they need pairwise logic are a tuple away from being a key.

Tuple keys carry multi-level order

Tuples compare left to right and stop at the first difference, so a tuple key is a list of sort levels in priority order.

people.sort(key=lambda p: (p.dept, -p.salary, p.name))

Department ascending, then salary descending, then name ascending as the tie-break. The -p.salary is the negation trick, and it works only on numbers. There is no -name.

The same four records sorted three times by one unchanged sort call, each key function producing a different order100%−+FitSVGEsc

Scroll to zoom · drag to pan · 0 fits · Esc closes

When a string field has to run opposite to a numeric one, you have two honest options. Flip the whole sort with reverse=True and negate the fields that should stay ascending, or run two passes and let stability do the work.

Stability is what makes two passes legal

A stable sort keeps elements whose keys compare equal in their original input order. Python's sort is Timsort and stability is documented, not incidental, so you may depend on it.

people.sort(key=lambda p: p.name, reverse=True)   # least significant key first
people.sort(key=lambda p: p.dept)                 # most significant key last

Sort by the weakest key first and the strongest key last. Each later pass only moves elements whose keys differ; the ones it considers equal keep whatever order the previous pass gave them. That single property is also what makes radix sort correct, and it is worth being able to state precisely, because interviewers ask.

Stability is not universal. C++'s std::sort gives no stability guarantee; std::stable_sort is the one that does. Java's Arrays.sort is a stable merge on objects and an unstable dual-pivot quicksort on primitives. If your answer depends on stability, say so out loud — in an unstable sort, two runs on the same input can legally disagree.

Custom alphabets: build a rank, then sort by rank

"Sort these words by this alphabet" is not a comparator problem. Turn the desired order into a lookup from value to position, then sort by position.

order = 'hlabcdefgijkmnopqrstuvwxyz'
rank  = {c: i for i, c in enumerate(order)}
words.sort(key=lambda w: [rank[c] for c in w])

A list of ranks compares element by element and treats a prefix as smaller, which is exactly dictionary order under the new alphabet. Building every key costs O(total characters) once; a comparator would redo that character lookup inside each of the ~n log₂ n comparisons.

The same shape covers every "sort in this arbitrary order" request: a priority string, a fixed status list, a column order the caller supplied. Decide what happens to values missing from the dict rather than letting a KeyError surface mid-sort — rank.get(v, len(order)) parks unknowns at the end.

A comparator that is not an ordering produces nonsense

Arrange [3, 30, 34, 5, 9] so the concatenation is the largest number. The tempting key is "descending as strings", which gives 9 5 34 30 3 and the answer 9534303. The correct answer is 9534330. The naive key ranks 30 above 3 because '30' > '3' lexicographically, while the concatenation cares about what follows.

The rule that works compares the two concatenations directly: a comes before b when a + b > b + a as strings.

from functools import cmp_to_key

nums = list(map(str, nums))                  # concatenate, do not add
def cmp(a, b):                               # -1, 0, +1 — the whole contract
    return (a + b < b + a) - (a + b > b + a)

nums.sort(key=cmp_to_key(cmp))               # ['9', '5', '34', '3', '30']

The str is load-bearing. On the integers [3, 30, 34, 5, 9] the + is addition, a + b > b + a is never true, the comparator returns 1 for every pair, and the list comes back in its original order — 3303459, not the 9534330 we were after. The comparator has to see '3' + '30' = '330' against '30' + '3' = '303'.

The 0 is load-bearing too. A three-way comparator must satisfy sgn(cmp(x, y)) == -sgn(cmp(y, x)), and -1 if a + b > b + a else 1 returns 1 in both directions when the two concatenations are equal, so '3' sorts strictly before itself. Python survives that because cmp_to_key only ever calls __lt__; Java's TimSort raises IllegalArgumentException on exactly this violation, and C++'s std::sort is undefined behaviour.

The relation underneath — a + b > b + a on strings — is a strict weak ordering: irreflexive, asymmetric, transitive, and the pairs it leaves tied are genuinely interchangeable, which is why every sort implementation agrees on the result. A sort is only entitled to produce a sensible answer when the order you hand it has those properties.

Break them and the failure is not a slightly wrong answer, it is unpredictable behaviour. A comparator like "treat scores within 5 points as tied, otherwise higher first" is not transitive across ties: 10 ties 14, 14 ties 18, but 10 does not tie 18. Java detects it and throws IllegalArgumentException out of the middle of the sort, C++'s std::sort has undefined behaviour and can run off the end of the array, and Python quietly returns an order that changes with the input permutation.

This particular comparator can also be turned back into a key. Repeat each string until it is longer than any concatenation of two of them — for values below 10 digits, key=lambda s: s * 20 with reverse=True — and plain descending order on the repeated strings agrees with the concatenation order, for n key calls instead of 2 × 10⁷ comparisons.

In an interview

Say the key out loud before you write it: "I want department ascending, salary descending, so the key is the tuple (dept, -salary)." That one sentence demonstrates that you know the sort is a detail and the order is the design.

When the order is unusual, name the property you are relying on. "This is a valid strict weak ordering because a+b > b+a is transitive" and "this two-pass approach is correct because Python's sort is stable" are the two sentences that turn a working solution into a defended one. See the solving loop for where that sentence belongs in the conversation.

The mistake that loses points: writing a comparator because the order looks pairwise, then being unable to say whether it is transitive. If you cannot defend the ordering, you cannot defend the output.

Check yourself

You need employees sorted by department ascending and name descending, both strings. Write it without a comparator.

Two stable passes, least significant first: sort by name with reverse=True, then sort by department. The second pass leaves equal departments in the reversed-name order the first pass built.

A comparator is called about how many times for n = 10⁵, and how many times is a key function called?

A comparator runs once per comparison: 10⁵ × 17 ≈ 1.7 × 10⁶ calls. A key runs once per element: 10⁵ calls. Same sort, seventeen times the interpreted work.

Your comparator returns 0 whenever two records are "close enough". What breaks, and how would you find out?

Transitivity of equality: a ties b, b ties c, a does not tie c. The sorted order then depends on the comparison sequence, so the same multiset in a different input order gives a different answer — which is exactly the test to run, shuffling the input and checking the output is unchanged.