Sorting with Custom Comparators

Almost every greedy on this phase begins with a sort. The algorithm is usually three lines; the sort key is the insight. “Sort by end time” is interval scheduling. “Sort by how much cheaper A is than B” is the solution to Two City Scheduling.

Python gives you two ways to express an ordering, and knowing which to reach for matters:

• key= — map each element to a value that sorts naturally. Fast, idiomatic, and correct for almost everything.
• cmp_to_key — define a pairwise comparison. Necessary only when the ordering genuinely cannot be expressed per-element.

This page covers both, plus the traps in mixed-direction sorting.

What you’ll learn

• Tuple keys for multi-level sorting, and negation for descending fields.
• Why negating a string is impossible, and what to do instead.
• functools.cmp_to_key — and how to recognise the rare case that needs it.
• Why sort stability is a feature you can design around.
• Three real LeetCode problems solved in the browser: 179, 406, 1029.

The cue

You are looking at a custom-comparator problem when…

• The ordering is not simply ascending on one field — 179, 406, 937.
• You must sort by several fields in different directions — 406, 692.
• The right ordering is a derived quantity, not a stored one — 1029 sorts by cost_a - cost_b, a value that appears nowhere in the input.
• Correctness depends on a pairwise rule that cannot be reduced to a per-element score — 179 is the classic.
• A greedy is obviously right once things are in the right order, and the whole problem is finding that order.

Visual intuition

The algorithm is never the interesting part — sorting is $O(n \log n)$ whichever one runs. The key is the answer. Here is one array sorted three ways:

sortSame four words, three keys, three different ordersthe key IS the algorithm

bb0a1ccc2dd3

original

bb0a1ccc2dd3

1words = ['bb', 'a', 'ccc', 'dd']2 3sorted(words)                       # 1. lexicographic (default)4sorted(words, key=len)              # 2. by length5sorted(words, key=lambda s: (len(s), s))   # 3. length, then alphabet

n4

inputOne array, three questions. Sorting is $O(n \log n)$ whichever key you pick, so the algorithm is never the interesting part here — **the key is the answer**. Watch how the same four words land in three different orders.

Play‹›1/4⟲

Watch the tie in step 3: 'bb' and 'dd' have equal length, and Python's sort is stable, so they keep their original relative order. That guarantee is what makes the tuple key (len, s) an explicit tie-break rather than a hope.

Tool 1 — tuple keys

Tuples compare lexicographically, so a tuple key sorts by the first field, then breaks ties with the second, and so on.

tuple_keys.py

people = [("alice", 30), ("bob", 25), ("carol", 30)]
 
print(sorted(people, key=lambda p: p[1]))              # by age ascending
print(sorted(people, key=lambda p: -p[1]))             # by age descending
print(sorted(people, key=lambda p: (-p[1], p[0])))     # age desc, then name asc

That last line is the pattern worth memorising: negate the fields you want descending, leave the rest ascending. It handles mixed directions in a single pass with no comparator function.

You cannot negate a string

key=lambda s: -s is a TypeError. For a descending string field you have three options:

1. Sort twice, relying on stability — sort by the secondary key first, then by the primary. Python’s sort is stable, so the first ordering survives within equal primary keys.
2. reverse=True — but that reverses every field, which is usually wrong when directions are mixed.
3. cmp_to_key — always available, slower.

Option 1 is the idiomatic fix. For “count descending, word ascending”:

python

words.sort()                                    # secondary: word ascending
words.sort(key=lambda w: counts[w], reverse=True)   # primary: count descending

Because the second sort is stable, words with equal counts keep the alphabetical order established by the first. This exact pair of lines solves LC 692.

Tool 2 — cmp_to_key for pairwise rules

Some orderings cannot be expressed as a per-element key at all. LC 179 is the canonical example: to build the largest number from [3, 30, 34, 5, 9], you need "3" before "30" because "330" > "303" — a fact about the pair, not about either string alone.

cmp_to_key.py

from functools import cmp_to_key
 
 
def compare(a, b):
    """Return negative if a should come first, positive if b should."""
    if a + b > b + a:
        return -1          # a first
    if a + b < b + a:
        return 1           # b first
    return 0               # equal
 
 
nums = ["3", "30", "34", "5", "9"]
print(sorted(nums, key=cmp_to_key(compare)))    # ['9', '5', '34', '3', '30']

The convention is C’s: negative means “first argument comes first”, positive means the second does, zero means equal. Getting the sign backwards silently reverses your sort.

Is 179’s ordering really not expressible as a key?

There is a well-known trick — key=lambda s: s * 10 — that works for LC 179 because the constraints bound each number to 10 digits, so repeating a string enough times makes plain lexicographic comparison agree with the pairwise rule. It is clever and worth mentioning.

But it relies on that bound. cmp_to_key expresses the rule directly with no hidden assumption, which is why it is the better answer to write and defend. Mention the trick to show you spotted it; ship the comparator.

	Speed	When to use
key=	Fast — computes n keys, then sorts	Almost always
cmp_to_key	Slower — wraps every element, calls Python per comparison	Only when the rule is inherently pairwise

Dry run

LC 179 — largest number from [3, 30, 34, 5, 9]. The comparison is about the pair, not either element:

pair	a + b	b + a	verdict
"3", "30"	330	303	3 first — even though 30 is the larger number
"30", "34"	3034	3430	34 first
"5", "9"	59	95	9 first

Sorted: 9 5 34 3 30 → 9534330.

• Plain descending sort gives 9534303 — off by 27, and only in the last two digits. It looks almost right, which is exactly why this problem is asked: "30" > "3" lexicographically, but "330" > "303" is what actually matters.
• No per-element key can express this. A key maps each element to a value independently, and here the correct position of "3" depends on what it is being compared against. That is the precise condition for reaching for cmp_to_key.
• The s * 10 trick works only because of the constraints. Repeating each string past the maximum length makes lexicographic order agree with the pairwise rule — clever, but it depends on a bound the problem happens to give. cmp_to_key states the intent directly.

LC 406 — reconstruct the queue from [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]. Sort by height descending, then k ascending: [7,0] [7,1] [6,1] [5,0] [5,2] [4,4]. Then insert each person at index k:

insert	at index	queue after
[7,0]	0	[[7,0]]
[7,1]	1	[[7,0],[7,1]]
[6,1]	1	[[7,0],[6,1],[7,1]]
[5,0]	0	[[5,0],[7,0],[6,1],[7,1]]
[5,2]	2	[[5,0],[7,0],[5,2],[6,1],[7,1]]
[4,4]	4	[[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]

• Tallest-first is what makes insertion safe. Everyone already placed is at least as tall as the person being inserted, so inserting at index k puts exactly k taller-or-equal people in front — and shorter people added later never disturb that count, because they do not count toward anyone’s k.
• The k-ascending tie-break is not decoration. Among equal heights, inserting the smaller k first keeps both correct; reversed, the second insertion displaces the first.
• The sort is the algorithm. The insertion loop is three lines and would be meaningless under any other order.

Complexity

Approach	Time	Space	Notes
sorted(xs) / .sort()	$O(n \log n)$	$O(n)$ / $O(1)$-ish	Timsort; .sort() is in place
key= function	$O(n \log n)$, n key calls	$O(n)$ for the keys	the key is computed once per element, not once per comparison
Tuple key	same	same	comparison is lexicographic, element by element
cmp_to_key	$O(n \log n)$, $O(n \log n)$ comparator calls	$O(n)$ wrapper objects	noticeably slower — a Python call per comparison
Two-pass stable sort	$2 \times O(n \log n)$	—	sort by the secondary key first, then the primary
LC 406 insertion loop	$O(n^2)$	$O(n)$	list insertion is $O(n)$; the sort is not the bottleneck

Why key= beats cmp_to_key in practice: the key function runs exactly n times and the comparisons then happen in C. A cmp_to_key comparator is a Python-level call on every comparison — roughly $n \log n$ of them — which is typically several times slower. Reach for it only when the ordering genuinely cannot be expressed per element.

Stability, and the two-pass trick it enables

Python’s sort is stable: equal keys keep their original relative order. That is a documented guarantee, not an implementation detail, and it buys you compound orderings without tuples:

python

words.sort(key=lambda w: w)            # secondary key first
words.sort(key=lambda w: counts[w], reverse=True)   # then primary

The second sort preserves the first’s order within each count group. Useful when the primary key needs reverse=True and the secondary does not — the case where a single tuple key cannot express it, since you cannot negate a string.

The variant map

Variant	The ordering	Canonical problem
Pairwise concatenation	a + b vs b + a via cmp_to_key	179 Largest Number
Mixed directions	Tuple key (-height, k)	406 · 692
Derived quantity	Sort by cost_a - cost_b	1029 Two City Scheduling
Descending string field	Two stable sorts, secondary first	692 Top K Frequent Words
Category then content	Tuple key with a category flag first	937 Reorder Data in Log Files
Sort to enable a greedy	Sort by end / by start	Interval scheduling

Practice — real LeetCode problems

LC 179 — Largest Number · Medium

Problem. Given a list of non-negative integers, arrange them so that they form the largest possible number. Return it as a string.

Constraints. 1 <= len(nums) <= 100, 0 <= nums[i] <= 10^9.

Examples. [10,2] gives "210" · [3,30,34,5,9] gives "9534330" · [0,0] gives "0"

pch.exerciseTag pch.exerciseTitle

Editorial — approach, complexity, follow-ups

The ordering is pairwise: a should precede b exactly when the concatenation a + b is larger than b + a. No per-element score captures this, because whether "3" beats "30" depends on "30".

Time $O(n \log n)$ comparisons, each $O(L)$ on string length, so $O(n L \log n)$. Space $O(nL)$.

Two details:

• The all-zeros guard. [0,0] sorts to ["0","0"] and joins to "000" — wait, to "00" — either way not "0". Since the comparator puts the largest first, if the leading character is "0" then every element is zero, so the answer is "0". Checking result[0] == "0" is sufficient and cheaper than stripping.
• Transitivity. This comparator is a valid total order (the relation a+b > b+a is transitive on digit strings), which is what makes it safe to hand to a sort. A non-transitive comparator produces undefined results, and it is a fair thing to be asked about.

[432, 43, 43] giving "4343432" is the case that catches naive descending sorts: plain string-descending order would put "432" first and produce "4324343", which is smaller.

Follow-ups you should expect: “Can you avoid cmp_to_key?” — yes, the key=lambda s: s * 10 trick, valid because values are bounded to 10 digits; say why it works and why the comparator is safer. “Prove the comparator is transitive” — a legitimate deeper question. “Smallest number instead?” — flip the comparison, and mind leading zeros differently.

LC 406 — Queue Reconstruction by Height · Medium

Problem. Each person is [h, k]: height h, and k = the number of people in front of them with height greater than or equal to h. Reconstruct and return the queue.

Constraints. 1 <= len(people) <= 2000, 0 <= h <= 10^6, 0 <= k < len(people). A valid queue is always possible.

Examples. [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]] gives [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]

pch.exerciseTag pch.exerciseTitle

Editorial — approach, complexity, follow-ups

Process people tallest first. When you insert someone, everyone already in the list is at least as tall, so among those people the person’s k is exactly their target index — insert them there.

And inserting a shorter person later never invalidates an earlier placement, because k counts only people of height >= h. A shorter person does not count towards anyone taller. That monotonicity is why the greedy works.

Time $O(n^2)$ — list.insert shifts $O(n)$ elements, n times. Space $O(n)$. This is accepted at n <= 2000; a Fenwick tree or balanced BST that finds the “k-th empty slot” reduces it to $O(n \log n)$, which is the optimisation to name if pushed.

The tuple key (-p[0], p[1]) is the crux:

• -p[0] gives descending height.
• p[1] gives ascending k within equal heights. This part is essential, not cosmetic: among people of the same height, the one with smaller k must be inserted first, or they would land behind their same-height peer and both counts would be wrong. Try [[7,0],[7,1]] with the k order reversed and the output is [[7,1],[7,0]], which is invalid.

Follow-ups you should expect: “Why tallest first?” — so that everyone already placed counts towards k, making k an exact index. “Why is k ascending within a height?” — as above; a great test of whether you reasoned or memorised. “Reduce the $O(n^2)$?” — Fenwick tree over empty slots, or a segment tree, for $O(n \log n)$. “What if k counted strictly taller people?” — the same-height tie-break changes, and you must re-derive it.

LC 1029 — Two City Scheduling · Medium

Problem. 2n candidates must be flown to interviews. costs[i] = [aCost, bCost] gives the cost of flying candidate i to city A or city B. Exactly n must go to each city. Return the minimum total cost.

Constraints. 2 <= len(costs) <= 100, len(costs) is even, 1 <= aCost, bCost <= 1000.

Examples. [[10,20],[30,200],[400,50],[30,20]] gives 110 · [[259,770],[448,54],[926,667],[184,139],[840,118],[577,469]] gives 1859

pch.exerciseTag pch.exerciseTitle

Editorial — approach, complexity, follow-ups

Send everyone to city B as a baseline, costing sum(bCost). Moving person i to A instead changes the total by aCost[i] - bCost[i]. You must move exactly n people, so choose the n with the smallest (most negative) differences.

Sorting by c[0] - c[1] puts exactly those first, so the answer is the A costs of the first half plus the B costs of the second.

Time $O(n \log n)$. Space $O(1)$ beyond the sort.

The lesson is the derived key: aCost - bCost appears nowhere in the input, and no ordering of aCost or bCost alone solves the problem. Sorting by aCost ascending fails — someone cheap for A might be even cheaper for B, and the exact-split constraint is what makes only the difference meaningful.

An exchange argument confirms optimality: if an optimal assignment sends p to B and q to A where diff(p) < diff(q), swapping them changes the total by diff(p) - diff(q) < 0, an improvement. So no optimal solution can have such an inversion, which is exactly what sorting by difference eliminates.

Follow-ups you should expect: “Why not sort by aCost?” — the counterexample above. “Prove it” — the exchange argument. “What if the split were k and 2n - k?” — same sort, split at k. “What if there were three cities?” — greedy breaks; it becomes min-cost flow or DP over counts, a genuinely harder problem worth flagging.

LeetCode problem set

Generated from the problem database, so each entry carries its sheet membership and reported companies. Tick them off as you go — progress is saved in this browser, and the Export button writes it to a file you can keep.

LC 937 is a stability problem in disguise

Reorder Data in Log Files asks that letter-logs come first (sorted by content, then identifier) while digit-logs keep their original relative order.

That second requirement is exactly what a stable sort provides for free. Give every digit-log an identical sort key and Python’s stability preserves their input order with no extra work:

python

def key(log):
    ident, rest = log.split(" ", 1)
    if rest[0].isdigit():
        return (1,)              # all digit-logs tie -> stability keeps order
    return (0, rest, ident)      # letter-logs: content, then identifier
logs.sort(key=key)

Knowing that Python’s sort and sorted are guaranteed stable — and designing a key that exploits it — is a genuinely useful piece of language knowledge.

7 problems

0 easy6 medium1 hard

Work down the ladder. Tick each problem off as you go — progress is saved in this browser, and the Export button in the filter bar writes it to a file you can keep.

AllEasyMediumHard

Unsolved onlyExportImportReset

• ○179Largest NumbermediumPairwise `a+b` vs `b+a`; needs `cmp_to_key`
• ○406Queue Reconstruction by HeightmediumTuple key `(-h, k)`, then insert at index `k`
• ○692Top K Frequent WordsmediumCount descending **and** word ascending -- two stable sorts, or a `(-count, word)` key
• ○853Car FleetmediumNeetCode 150
• ○937Reorder Data in Log FilesmediumCategory first, then content, then identifier -- and digit logs keep original order (stability)
• ○1029Two City SchedulingmediumSort by the derived `aCost - bCost`
• ○354Russian Doll Envelopeshard

Interview follow-ups

They ask	What they’re checking	The answer
“key or cmp_to_key?”	Judgement	key unless the rule is inherently pairwise; cmp_to_key wraps every element and calls back into Python, so it is slower
“Sort descending on a string field?”	Language fluency	You cannot negate a string: use two stable sorts (secondary first), or a comparator
“Is Python’s sort stable?”	Useful detail	Yes, guaranteed — and you can design keys that rely on it (LC 937)
“Why does the tie-break direction matter in 406?”	Whether you reasoned it out	Among equal heights, smaller k must be inserted first, or same-height people land in the wrong order
“Prove your ordering is optimal”	Rigour	An exchange argument: show that any inversion relative to your order can be swapped for an improvement
“Is your comparator a valid total order?”	Depth	It must be transitive, or the sort’s behaviour is undefined — worth checking for cmp_to_key rules
“Can you avoid the $O(n^2)$ inserts in 406?”	Optimisation	A Fenwick tree or segment tree over empty slots gives $O(n \log n)$

Edge-case checklist

• All zeros (LC 179) — must return "0", not "00".
• Single element — every sort is trivially correct; check the wrapper code still works.
• Ties on the primary key — the case that reveals whether your secondary direction is right.
• Equal heights in LC 406 — [[7,0],[7,1]]; the tie-break test.
• Negative derived keys (LC 1029) — aCost - bCost is often negative; do not assume a sign.
• Descending string fields — reach for two stable sorts, never -string.
• Duplicate elements — fine, but make sure your comparator returns 0 for genuinely equal items rather than an arbitrary sign.
• Comparator sign convention — negative means the first argument comes first; reversing it silently inverts the whole sort.

Self-check

pch.quizTag Custom comparators — self-check

1. When is `cmp_to_key` genuinely necessary rather than just convenient?

   A Whenever the sort has two criteria B When the ordering depends on the PAIR rather than on either element alone — LC 179 needs '3' before '30' because '330' > '303', which no per-element key can express C Whenever you need descending order D When sorting strings
   pch.quizShowAnswer

   B — When the ordering depends on the PAIR rather than on either element alone — LC 179 needs '3' before '30' because '330' > '303', which no per-element key can express — A key maps each element independently. If the right position of an element depends on what it is compared against, no key exists — that is the precise test.

2. Why is `key=` preferred over `cmp_to_key` when both work?

   A cmp_to_key is deprecated B The key function runs exactly n times and the comparisons then happen in C, whereas a comparator is a Python-level call on every one of the ~n log n comparisons C key= is stable and cmp_to_key is not D cmp_to_key cannot handle ties
   pch.quizShowAnswer

   B — The key function runs exactly n times and the comparisons then happen in C, whereas a comparator is a Python-level call on every one of the ~n log n comparisons — Both are O(n log n) in the abstract; the constant differs by several times. Naming the reason — n key calls versus n log n Python calls — is the substantive answer.

3. You need to sort by count DESCENDING then by word ASCENDING. Why can't a single tuple key do it?

   A It can: key=(-count, word) B It can here, because count is numeric and negatable — but if the primary key were a STRING needing reverse order there is no negation, and the fix is two stable passes: secondary first, then primary with reverse=True C Tuples cannot mix types D reverse=True is not allowed with key=
   pch.quizShowAnswer

   B — It can here, because count is numeric and negatable — but if the primary key were a STRING needing reverse order there is no negation, and the fix is two stable passes: secondary first, then primary with reverse=True — The tuple trick relies on being able to negate. `key=lambda s: -s` on a string is a TypeError, and that is exactly when the two-pass stable sort earns its place.

4. What does the sign convention in a `cmp_to_key` comparator mean?

   A Positive means the first argument comes first B Negative means the FIRST argument comes first, positive means the second, zero means equal — C's convention, and getting it backwards silently reverses the sort C It must return True or False D It must return the smaller element
   pch.quizShowAnswer

   B — Negative means the FIRST argument comes first, positive means the second, zero means equal — C's convention, and getting it backwards silently reverses the sort — Silently reversed is the dangerous part: the code runs and produces a plausible ordering. Writing one example comparison by hand before trusting it is worth the ten seconds.

5. In LC 406, why sort by height descending before inserting at index k?

   A To make insertion O(1) B Because everyone already placed is at least as tall, so inserting at index k puts exactly k taller-or-equal people ahead — and shorter people added later never count toward anyone's k C Because k is always less than the height D To keep the sort stable
   pch.quizShowAnswer

   B — Because everyone already placed is at least as tall, so inserting at index k puts exactly k taller-or-equal people ahead — and shorter people added later never count toward anyone's k — The k-ascending tie-break among equal heights matters too: reversed, the second insertion displaces the first. The sort is the algorithm; the insertion loop is three lines.

6. Does Python's sort guarantee stability?

   A No, it is an implementation detail B Yes — it is a documented guarantee, which is what makes the two-pass compound sort (secondary key first, then primary) reliable rather than lucky C Only for lists of numbers D Only when using key=
   pch.quizShowAnswer

   B — Yes — it is a documented guarantee, which is what makes the two-pass compound sort (secondary key first, then primary) reliable rather than lucky — Because it is guaranteed rather than incidental, you can build compound orderings by sorting repeatedly — and the trace on this page shows equal-length words keeping their input order under key=len.

Recall card

• Cue — the sort order is not the natural one: multiple criteria, mixed directions, or a rule about pairs.
• Default reach — a tuple key: key=lambda x: (-x.count, x.name). Compared element by element, so it expresses “primary, then tie-break” directly.
• Negation only works on numbers. key=lambda s: -s on a string is a TypeError.
• Two stable passes for mixed directions on non-negatable keys: sort by the secondary key first, then the primary with reverse=True.
• Stability is guaranteed in Python — equal keys keep their input order.
• cmp_to_key only when the order depends on the pair (LC 179: a + b > b + a). Sign convention is C’s: negative = first argument first.
• Cost — $O(n \log n)$ either way, but key= runs n times in Python and compares in C, while a comparator is a Python call per comparison.
• The sort is often the whole algorithm — LC 406’s insertion loop is three lines and only works because of the height-descending, k-ascending order.

Recap

• In most greedy problems the algorithm is trivial and the sort key is the insight.
• Tuple keys handle multi-level ordering; negate the fields you want descending: (-height, k).
• You cannot negate a string. Use two stable sorts, secondary key first.
• cmp_to_key is for genuinely pairwise rules like LC 179’s a+b vs b+a. Negative means the first argument comes first, and the relation must be transitive.
• Python’s sort is stable, and that is a feature you can design keys around (LC 937).
• The best keys are often derived quantities the input never states — aCost - bCost in LC 1029 is the whole solution.
• Whatever ordering you choose, be ready to justify it with an exchange argument.

Next: the linked-list patterns — fast/slow pointers, in-place reversal, and dummy-head rewiring.