Python Sort for Coding Interviews: `key`, `cmp_to_key`, and Every Trap

You have a list of intervals. The algorithm says sort by end time. You write:

intervals.sort(key=lambda x: x[1])

Done. One line. Move on.

Then the next problem says: arrange a list of integers so they form the largest possible number. You write the same style of lambda and it gives the wrong answer. Because this time a simple key doesn't work. You need to compare two elements against each other directly, and the key parameter cannot express that.

Python sort has two modes in a coding interview. One obvious, one not. The obvious one handles 90% of problems. The non-obvious one shows up exactly when the stakes are highest and you have 12 minutes left.

---

sorted() vs .sort(): The One That Returns None

These look identical and behave almost identically. The difference is one line that fails silently:

nums = [3, 1, 2]
result = nums.sort()    # result is None
result = sorted(nums)   # result is [1, 2, 3]

.sort() is in-place and returns None. sorted() returns a new list.

In an interview, writing return nums.sort() returns None to the caller. Tests fail. No error appears. You spend the last five minutes debugging your algorithm when your algorithm is completely fine. It was the return statement. It was always the return statement. You will think about this at 2am for years.

The rule: use .sort() when you want to mutate the list and don't need the return value. Use sorted() when you need to keep the original or assign the result somewhere. Both take the same key and reverse parameters.

The exact energy of return nums.sort() watching all five test cases fail with no explanation.

---

The key Parameter: 90% of Interview Sorting

The key function maps each element to a comparison value. Python sorts those comparison values and returns the elements in that order.

words = ["banana", "fig", "apple", "kiwi"]

words.sort(key=len)            # by length: ['fig', 'kiwi', 'apple', 'banana']
words.sort(key=lambda w: w[-1])  # by last character
words.sort(key=str.lower)      # case-insensitive

The key function runs once per element, not once per comparison. Python evaluates key(x) for each element upfront, stores the results, and sorts from there. If your key is expensive to compute, this is a good thing. Python already thought of it.

Multi-criteria sorting with tuple keys

When you need to sort by two criteria (primary, then tiebreak), return a tuple:

students = [("Alice", 90), ("Bob", 85), ("Carol", 90)]

# Sort by score descending, then name ascending
students.sort(key=lambda s: (-s[1], s[0]))
# [('Alice', 90), ('Carol', 90), ('Bob', 85)]

The negation trick: negate a numeric field to flip its sort direction while keeping the tuple structure. (-score, name) sorts score descending and name ascending in one pass, no second call needed. Satisfying once you know it. Completely non-obvious the first time.

The interval sorting pattern

Interval problems almost always sort by start or by end time:

intervals.sort(key=lambda x: x[0])  # by start
intervals.sort(key=lambda x: x[1])  # by end

For the merge intervals and activity selection families, sorting by end time is what makes the greedy proof hold. A wrong sort key breaks algorithm correctness, not just performance. The answer looks reasonable. The tests say otherwise.

---

Python's Sort Is Stable. That's Worth Understanding.

Equal elements maintain their original relative order after sorting. This has been true since Python 2.3 and is a language guarantee, not an implementation detail. Python used Timsort through 3.10 and switched to the more efficient Powersort in 3.11. Both are stable.

Stability has a practical consequence: you can chain sort calls in reverse priority order and get the right result.

# Sort by score descending, then by name ascending
records.sort(key=lambda r: r["name"])      # secondary sort first
records.sort(key=lambda r: -r["score"])   # primary sort second

Because the second sort is stable, equal-score records preserve the name ordering from the first pass. The tuple key approach is cleaner for most cases, but the sequential technique is useful when the secondary key is inconvenient to restate as a lambda.

For why stability matters beyond Python, including its role in making multi-pass radix sort correct, see Stable Sort.

---

When key Breaks: Enter cmp_to_key

The key parameter works when you can map each element to a value and compare those values. It breaks when the comparison depends on both elements simultaneously.

The canonical interview example is LeetCode 179, "Largest Number":

Given a list of non-negative integers, arrange them so they form the largest number.

Input: [3, 30, 34, 5, 9] Output: "9534330"

The first instinct is to sort descending by value. It fails. 30 placed before 3 gives "303", but 3 before 30 gives "330", which is larger. The right ordering of any pair a, b depends on whether str(a) + str(b) or str(b) + str(a) is larger. That comparison involves both elements at once. A key function that sees only one element at a time cannot express it.

from functools import cmp_to_key

def largest_number(nums: list[int]) -> str:
    def compare(a: str, b: str) -> int:
        if a + b > b + a:
            return -1   # a should come first
        elif a + b < b + a:
            return 1    # b should come first
        return 0

    strs = list(map(str, nums))
    strs.sort(key=cmp_to_key(compare))
    return "0" if strs[0] == "0" else "".join(strs)

cmp_to_key wraps a comparator function into an object that implements __lt__, __gt__, and the rest of the rich comparison methods. Python's sort uses those methods internally.

The sign convention: negative means "a comes first" (a is less than b in sort order). Positive means "b comes first". This matches C's strcmp and Java's Comparator.compare. Test your convention with a small example before trusting it, because you will get it backwards the first time. You might get it backwards the second time too. It is that specific kind of thing.

The Python 2 cmp parameter was removed in Python 3. functools.cmp_to_key is the replacement and has been available since Python 2.7 and 3.2.

Other cases where cmp_to_key appears

• Version strings: "1.9.0" vs "1.11.0" (lexicographic sort puts 9 > 11, wrong)
• Sorting with conditional field priority (sort by field A if nonzero, else field B)
• Any comparison whose logic requires seeing both elements to make a decision

Flip the sign in your comparator. Watch everything sort backwards. Flip it back. Watch it work. Never fully trust it again.

---

reverse=True vs Negating the Key

Both reverse the sort direction. They are not equivalent.

nums = [3, 1, 2]
sorted(nums, reverse=True)       # [3, 2, 1]
sorted(nums, key=lambda x: -x)   # [3, 2, 1]

Same result here. The difference matters in three places:

Strings. You can't negate a string. reverse=True works cleanly. To sort words by descending length: sorted(words, key=len, reverse=True).

Mixed-criteria tuples. To sort by score descending and name ascending, you negate only the numeric field: key=lambda s: (-s[1], s[0]). Using reverse=True flips both fields, including the name, which you didn't want.

Non-numeric types generally. Negation only works on numbers. For anything else, reverse=True is the right lever for a full-list reversal.

Use negation when one numeric field inside a tuple needs to flip. Use reverse=True for flipping an entire sort with a single key.

---

Sorting Characters in a String

Two patterns appear in almost every string problem:

s = "dcab"
sorted_s = "".join(sorted(s))   # "abcd"

sorted() works on any iterable, including strings, and returns a list of characters. "".join(...) reassembles them. The "".join(sorted(s)) idiom is the standard anagram check: two strings are anagrams if and only if sorted(a) == sorted(b). It's O(n log n), which is fine at interview scale.

For sorting by character frequency:

from collections import Counter

freq = Counter(s)
chars = sorted(freq, key=lambda c: -freq[c])

This returns characters ordered from most to least frequent. Combine with key=lambda c: (-freq[c], c) to break ties alphabetically.

For a broader Python built-in reference, see Python Interview Cheat Sheet.

---

The heapq Gap

heapq doesn't accept a key or comparator parameter. heapq is always a min-heap on the raw element. Candidates who expect it to work like sorted() get surprised. There's nothing to configure. Python decided not to.

For a max-heap, negate the values:

import heapq

nums = [3, 1, 4, 1, 5]
max_heap = [-x for x in nums]
heapq.heapify(max_heap)
top = -heapq.heappop(max_heap)   # 5

For complex objects, put the priority as the first element of a tuple:

heapq.heappush(heap, (distance, node_id))

The tuple trick extends naturally to multi-field priority: (distance, tiebreak_id) gives a min-heap by distance, tiebroken by ID. This is the standard Dijkstra pattern. The heap compares tuples element by element, so it uses distance as the primary key and tiebreak_id only on ties.

For custom-class objects, implement __lt__ on the class rather than relying on cmp_to_key. heapq doesn't use cmp_to_key at all. In fact, looking for a key parameter in the heapq docs is a short journey that ends in mild frustration.

For heap internals and the heapify amortized O(n) proof, see The Heap Data Structure.

---

Python Sort Quick Reference

Goal	Code
Sort ascending	nums.sort() or sorted(nums)
Sort descending	nums.sort(reverse=True)
Sort by field	items.sort(key=lambda x: x[1])
Sort by multiple fields	items.sort(key=lambda x: (x[1], x[0]))
One field descending, one ascending	items.sort(key=lambda x: (-x[1], x[0]))
Sort strings case-insensitive	words.sort(key=str.lower)
Sort by descending length	words.sort(key=len, reverse=True)
Custom pairwise comparator	items.sort(key=cmp_to_key(compare_fn))
Sort characters in a string	"".join(sorted(s))
Max-heap with heapq	heapq.heappush(h, -val)
Custom priority in heapq	heapq.heappush(h, (priority, item))

---

Five Mistakes That Cost Marks

1. Returning .sort(). nums.sort() returns None. Writing return nums.sort() fails silently. Assign sorted() instead, or sort in place and return nums on a separate line.

2. Writing a comparator and passing it directly. Python's sort doesn't call comparator functions directly. It calls __lt__ on key objects. A bare key=compare_fn where compare_fn takes two arguments does not work. You need key=cmp_to_key(compare_fn). The error message when you get this wrong is not helpful.

3. Getting the comparator sign backwards. Returning 1 when you mean "a comes first" and -1 when you mean "b comes first". Test explicitly: for "Largest Number", compare("3", "30") should return -1 because "330" > "303" so "3" belongs first. If it returns 1, your sort is flipped and your output looks almost right, which is somehow worse.

4. Using negation on non-numeric types. key=lambda x: -x breaks on strings, tuples, and anything else that isn't a number. For everything else, use reverse=True or restructure the key.

5. Assuming heapq accepts a key parameter. It doesn't. Use negation for max-heap on numbers, tuples for structured priority, or __lt__ on the class.

---

The Two Problems to Lock This In

LeetCode 179 (Largest Number) and 791 (Custom Sort String) are the two problems where cmp_to_key gives the cleanest solution. Solve both before your next interview cycle. The sign convention will feel natural after one or two reps.

Knowing the rules matters less than applying them while talking through your approach out loud. SpaceComplexity runs voice-based DSA mock interviews with rubric scoring. Sorting problems come up across medium and hard tiers, and the platform catches when your approach is sound but your sort key is subtly wrong.

---

Key Takeaways

• .sort() returns None. sorted() returns a new list. Never capture .sort()'s return value.
• The key function runs once per element, not once per comparison.
• Python's sort is stable. Multi-key sorts work cleanly via tuple keys or chained calls.
• Use cmp_to_key when comparison logic requires seeing both elements simultaneously.
• reverse=True flips the entire sort. Negation flips one numeric field within a tuple key.
• heapq has no comparator. Use negation for max-heap, tuples for structured priority.

---

Further Reading

• Python Sorting HOWTO (official docs, comprehensive examples)
• functools.cmp_to_key documentation (Python 3 reference)
• Timsort on Wikipedia (algorithm background)
• Powersort on Wikipedia (Python 3.11+ merge policy)