What Is Multi-Key Sorting?
Multi-key sorting orders data by falling back to the next key when the first one can't decide. It's essential for data like a coordinate (x, y), which has two values and can't be compared as a single number.
The rule is simple: "Compare by x first, and only when x ties, compare by y." We call x the primary key and y the secondary key.
Why Does It Matter?
Most real-world sorting is multi-key.
- •Coordinate sort: by x, then by y on ties (computational geometry, game maps)
- •Name sort: by last name, then by first name
- •Leaderboard: score descending, then time ascending
Coding interviews frequently say "output sorted by x ascending, then y ascending."
The Comparator Is the Core
Everything about multi-key sorting lives in the comparator.
compare(a, b):
if a.x != b.x: return a.x - b.x # primary key: x
return a.y - b.y # secondary key: y (only when x ties)When x differs, the decision is made right there. Only when x ties do we move on to y. This "next key only on a tie" flow is the essence of multi-key sorting.
How It Works (Example)
Let's sort points = [(3,1), (1,4), (3,0), (2,2)].
Step 1. Line them up by x → (1,4) / (2,2) / (3,0)·(3,1)
Step 2. (3,0) and (3,1) tie at x = 3, so decide by y → (3,0) comes first
Result. [(1,4), (2,2), (3,0), (3,1)]
The key takeaway: (3,0) comes before (3,1). Without the secondary key y, their order would not be guaranteed.
Time Complexity
| Method | Time |
|---|---|
| Demo with bubble sort | O(n²) |
| Real comparison sort (comparator) | O(n log n) |
The comparator itself is O(1) — constant time no matter how many keys, so the overall complexity is set by the sorting algorithm you use. The learning visualization uses bubble sort to show every comparison, but in practice you pass a comparator to a sort function and get O(n log n).
Common Mistakes
- •Dropping the secondary key: comparing only x leaves equal-x elements in an arbitrary order.
- •Misreading the tie condition: writing "also check y when x differs" gives wrong results. Check y only when x ties.
- •Sign confusion: ascending is
a - b, descending isb - a. Each key may go a different direction, so be careful.
See It in Action on AlgoNote
On AlgoNote you can watch, one step at a time, how the x-comparison step and the y-fallback step (on a tie) are separated.