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

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:

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

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.

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.

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.

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.

Dry run

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

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:

• 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

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.

The variant map

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"

Press Run to see what your code prints.

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]]

Press Run to see what your code prints.

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

Press Run to see what your code prints.

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.

Interview follow-ups

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

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.