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=key= — map each element to a value that sorts naturally. Fast, idiomatic, and correct for almost everything.
cmp_to_keycmp_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_keyfunctools.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

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

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.

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

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.
reverse=Truereverse=True — but that reverses every field, which is usually wrong when directions are mixed.
cmp_to_keycmp_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

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_keycmp_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][3, 30, 34, 5, 9], you need "3""3" before "30""30" because "330" > "303""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']

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.

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

The variant map

Variant	The ordering	Canonical problem
Pairwise concatenation	`a + ba + b` vs `b + ab + a` via `cmp_to_keycmp_to_key`	179 Largest Number
Mixed directions	Tuple key `(-height, k)(-height, k)`	406 · 692
Derived quantity	Sort by `cost_a - cost_bcost_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) <= 1001 <= len(nums) <= 100, 0 <= nums[i] <= 10^90 <= nums[i] <= 10^9.

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

Editorial — approach, complexity, follow-ups

The ordering is pairwise: aa should precede bb exactly when the concatenation a + ba + b is larger than b + ab + a. No per-element score captures this, because whether "3""3" beats "30""30" depends on "30""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][0,0] sorts to ["0","0"]["0","0"] and joins to "000""000" — wait, to "00""00" — either way not "0""0". Since the comparator puts the largest first, if the leading character is "0""0" then every element is zero, so the answer is "0""0". Checking result[0] == "0"result[0] == "0" is sufficient and cheaper than stripping.
Transitivity. This comparator is a valid total order (the relation a+b > b+aa+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][432, 43, 43] giving "4343432""4343432" is the case that catches naive descending sorts: plain string-descending order would put "432""432" first and produce "4324343""4324343", which is smaller.

Follow-ups you should expect: “Can you avoid cmp_to_keycmp_to_key?” — yes, the key=lambda s: s * 10key=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][h, k]: height hh, and kk = the number of people in front of them with height greater than or equal to hh. Reconstruct and return the queue.

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

Examples. [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]][[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]][[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]

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 kk is exactly their target index — insert them there.

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

Time $O(n^2)$ — list.insertlist.insert shifts $O(n)$ elements, nn times. Space $O(n)$ . This is accepted at n <= 2000n <= 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])(-p[0], p[1]) is the crux:

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

Follow-ups you should expect: “Why tallest first?” — so that everyone already placed counts towards kk, making kk an exact index. “Why is kk 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 kk counted strictly taller people?” — the same-height tie-break changes, and you must re-derive it.

LC 1029 — Two City Scheduling · Medium

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

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

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

Editorial — approach, complexity, follow-ups

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

Sorting by c[0] - c[1]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 - bCostaCost - bCost appears nowhere in the input, and no ordering of aCostaCost or bCostbCost alone solves the problem. Sorting by aCostaCost 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 pp to B and qq to A where diff(p) < diff(q)diff(p) < diff(q), swapping them changes the total by diff(p) - diff(q) < 0diff(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 aCostaCost?” — the counterexample above. “Prove it” — the exchange argument. “What if the split were kk and 2n - k2n - k?” — same sort, split at kk. “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

#	Problem	Difficulty	The twist
179	Largest Number	Medium	Pairwise `a+ba+b` vs `b+ab+a`; needs `cmp_to_keycmp_to_key`
406	Queue Reconstruction by Height	Medium	Tuple key `(-h, k)(-h, k)`, then insert at index `kk`
1029	Two City Scheduling	Medium	Sort by the derived `aCost - bCostaCost - bCost`
937	Reorder Data in Log Files	Medium	Category first, then content, then identifier — and digit logs keep original order (stability)
692	Top K Frequent Words	Medium	Count descending and word ascending — two stable sorts, or a `(-count, word)(-count, word)` key

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)

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 sortsort and sortedsorted are guaranteed stable — and designing a key that exploits it — is a genuinely useful piece of language knowledge.

Interview follow-ups

They ask	What they’re checking	The answer
”`keykey` or `cmp_to_keycmp_to_key`?”	Judgement	`keykey` unless the rule is inherently pairwise; `cmp_to_keycmp_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 `kk` 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_keycmp_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""0", not "00""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]][[7,0],[7,1]]; the tie-break test.
Negative derived keys (LC 1029) — aCost - bCostaCost - bCost is often negative; do not assume a sign.
Descending string fields — reach for two stable sorts, never -string-string.
Duplicate elements — fine, but make sure your comparator returns 00 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.

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)(-height, k).
You cannot negate a string. Use two stable sorts, secondary key first.
cmp_to_keycmp_to_key is for genuinely pairwise rules like LC 179’s a+ba+b vs b+ab+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 - bCostaCost - 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.

If this helped you, consider buying me a coffee ☕

Buy me a coffee

Sorting with Custom Comparators

What you’ll learn

The cue

Tool 1 — tuple keys

Tool 2 — cmp_to_keycmp_to_key for pairwise rules

The variant map

Practice — real LeetCode problems

LC 179 — Largest Number · Medium

LC 406 — Queue Reconstruction by Height · Medium

LC 1029 — Two City Scheduling · Medium

LeetCode problem set

Interview follow-ups

Edge-case checklist

Recap

Was this page helpful?

Tool 2 — `cmp_to_keycmp_to_key` for pairwise rules