Can Any Sort Go Faster? The n log n Speed Limit
Know whether a faster sort can exist before you hunt for one: why a faster machine, a tweaked quicksort or a cleverer comparison can't beat O(n log n) for a sort that compares, and the one kind of data where you can.
Freelancer · Data Structures · Updated
After this lesson you can
- Explain why no comparison sort can beat O(n log n) in the worst case
- Work out how many orders a few items can be in, and how many yes-or-no comparisons it takes to tell them apart
Key takeaways
- n items can be in n! orders (n factorial: n × (n - 1) × … × 1). Three cards have 6; eight cards have 40,320.
- A comparison is a yes-or-no question, and the best a yes-or-no question can do is rule out half of the orders still possible.
- Telling n! orders apart takes about log(n!) questions, which grows like n log n, so no comparison sort beats O(n log n) in the worst case.
- Merge sort already reaches that limit. Only sorts that don't compare, such as counting small whole numbers, can go faster.
- Ten million orders sorted by comparing take about 233 million comparisons; sorted by a status with 5 values, counting does it in about 10 million steps.
Before this: Sorting Without a Second Copy: Quicksort (merge sort and quicksort both sort in O(n log n)).
A shop's nightly report sorts its 10 million orders, and it finishes later every month. Your manager asks for it to be 10 times faster. The sort is already O(n log n): about 233 million comparisons.
What would you try?
A faster machine. Twice the speed, twice the bill, and twice as fast, not ten. Next year's 20 million orders take most of it back.
A cleverer quicksort. A better pivot and a tighter loop might save 20 or 30 percent. Each comparison gets cheaper, but there are still about 233 million of them.
A cleverer comparison, such as asking "which of these three is the smallest?" in one go. Inside, the computer still answers it with two or three yes-or-no comparisons, so the count hardly changes.
Every try makes the steps cheaper; none makes them fewer. So before hunting further, ask whether fewer is even possible.
The questions that lead to it
Merge sort is O(n log n). Quicksort is O(n log n) on a good day. Your language's built-in sort is O(n log n). Is that a coincidence, or could a cleverer idea do better? It's also an interview favorite ("can you sort faster than n log n?"). You won't need a proof here, only the idea, and the idea is a game you already know.
Twenty questions with a deck of cards
In the game Twenty Questions, one player thinks of something and the other asks yes-or-no questions. A good question splits what's still possible in half. With 20 questions you can tell apart about a million things, because 20 halvings of a million leaves one: the logarithm from How Many Times Can You Halve a Million? O(log n).
Sorting is the same game. Someone shuffles your cards, and your job is to find out which order they're in, so you can undo it. The only questions a sort like merge sort or quicksort can ask are comparisons: "is this card smaller than that one?", yes or no. A sort that learns about the items only by comparing them is a comparison sort, and every sort in this module is one.
How many orders?
Three cards, call them A, B and C, can be in 6 orders: ABC, ACB, BAC, BCA, CAB and CBA. There are 3 choices for the first card, then 2 for the second, then 1 for the last: 3 × 2 × 1 = 6. For n cards it's n × (n − 1) × … × 2 × 1, a number called n factorial and written n! (read "n factorial"). It grows terribly fast: 8 cards have 40,320 orders.
A comparison sort has to tell every one of those orders apart, since each needs different moves to undo. Each comparison has two answers, so it can at best rule out half of the orders still possible. Here are all the questions for three cards, drawn as a tree:

Six orders need at least 3 questions in the worst case, because 2 questions can only tell 4 things apart (2 × 2) and 6 is more than 4.
Counting the questions
This code works out, for 2, 4, 8 and 16 cards, how many orders there are, the fewest yes-or-no comparisons that can tell them all apart (keep doubling until the doubled number reaches the orders), and n log n, the speed of merge sort:
foreach (int n in new int[] { 2, 4, 8, 16 })
{
long orders = 1;
for (int i = 2; i <= n; i++)
{
orders *= i;
}
int questions = 0;
long reach = 1;
while (reach < orders)
{
reach *= 2;
questions++;
}
int halvings = 0;
for (int left = n; left > 1; left /= 2)
{
halvings++;
}
Console.WriteLine(n + " cards: " + orders + " orders; comparisons needed: at least " + questions + "; n log n: " + n * halvings);
}
2 cards: 2 orders; comparisons needed: at least 1; n log n: 2
4 cards: 24 orders; comparisons needed: at least 5; n log n: 8
8 cards: 40320 orders; comparisons needed: at least 16; n log n: 24
16 cards: 20922789888000 orders; comparisons needed: at least 45; n log n: 64
void main() {
for (int n : new int[] {2, 4, 8, 16}) {
long orders = 1;
for (int i = 2; i <= n; i++) {
orders *= i;
}
int questions = 0;
long reach = 1;
while (reach < orders) {
reach *= 2;
questions++;
}
int halvings = 0;
for (int left = n; left > 1; left /= 2) {
halvings++;
}
IO.println(n + " cards: " + orders + " orders; comparisons needed: at least " + questions + "; n log n: " + n * halvings);
}
}
2 cards: 2 orders; comparisons needed: at least 1; n log n: 2
4 cards: 24 orders; comparisons needed: at least 5; n log n: 8
8 cards: 40320 orders; comparisons needed: at least 16; n log n: 24
16 cards: 20922789888000 orders; comparisons needed: at least 45; n log n: 64
for n in [2, 4, 8, 16]:
orders = 1
for i in range(2, n + 1):
orders *= i
questions = 0
reach = 1
while reach < orders:
reach *= 2
questions += 1
halvings = 0
left = n
while left > 1:
left //= 2
halvings += 1
print(f"{n} cards: {orders} orders; comparisons needed: at least {questions}; n log n: {n * halvings}")
2 cards: 2 orders; comparisons needed: at least 1; n log n: 2
4 cards: 24 orders; comparisons needed: at least 5; n log n: 8
8 cards: 40320 orders; comparisons needed: at least 16; n log n: 24
16 cards: 20922789888000 orders; comparisons needed: at least 45; n log n: 64
for (const n of [2, 4, 8, 16]) {
let orders = 1;
for (let i = 2; i <= n; i++) {
orders *= i;
}
let questions = 0;
let reach = 1;
while (reach < orders) {
reach *= 2;
questions++;
}
let halvings = 0;
for (let left = n; left > 1; left = Math.floor(left / 2)) {
halvings++;
}
console.log(`${n} cards: ${orders} orders; comparisons needed: at least ${questions}; n log n: ${n * halvings}`);
}
2 cards: 2 orders; comparisons needed: at least 1; n log n: 2
4 cards: 24 orders; comparisons needed: at least 5; n log n: 8
8 cards: 40320 orders; comparisons needed: at least 16; n log n: 24
16 cards: 20922789888000 orders; comparisons needed: at least 45; n log n: 64
for (const n of [2, 4, 8, 16]) {
let orders = 1;
for (let i = 2; i <= n; i++) {
orders *= i;
}
let questions = 0;
let reach = 1;
while (reach < orders) {
reach *= 2;
questions++;
}
let halvings = 0;
for (let left = n; left > 1; left = Math.floor(left / 2)) {
halvings++;
}
console.log(`${n} cards: ${orders} orders; comparisons needed: at least ${questions}; n log n: ${n * halvings}`);
}
2 cards: 2 orders; comparisons needed: at least 1; n log n: 2
4 cards: 24 orders; comparisons needed: at least 5; n log n: 8
8 cards: 40320 orders; comparisons needed: at least 16; n log n: 24
16 cards: 20922789888000 orders; comparisons needed: at least 45; n log n: 64
A note on the languages: 16! is about 21 trillion, too big for an int, so C# and Java use long. Python's whole numbers never overflow, and JavaScript's numbers hold this one exactly. The table stops at 16 because 21! is too big even for a long.
The "comparisons needed" column is the logarithm of n!: how many times you can halve n! before one order is left. Compare it with the last column. The two numbers aren't equal, but they grow the same way: from 8 cards to 16, the first goes from 16 to 45 and the second from 24 to 64, both a little under three times as much. That's no accident. n! multiplies n numbers together, and about half of them are at least n ÷ 2, so its logarithm is roughly n halvings' worth of n: about n log n.
What the limit means
Put it together. Any comparison sort must tell all n! orders apart; each comparison at best halves them; so in the worst case it needs about log(n!) comparisons, which grows like n log n. That's a lower bound: a floor that no comparison sort, however clever, can get under. It's why every fast sort you'll meet is O(n log n), and why merge sort, which reaches the floor on every list, is as fast as a comparison sort can be in the worst case.
Two things the limit doesn't say:
- It's about growth, not seconds. Quicksort and a well-tuned built-in sort still beat a plain merge sort on real data, because their steps are cheaper. They can't change the n log n, only the time each step takes.
- It's only for sorts that compare. If the items are small whole numbers, you can sort without comparing. To sort a million test scores from 0 to 100, count how many of each score there are (101 counters, one pass), then write them out in order: O(n) work. That's counting sort, and it works because it never asks "is this one smaller?".
Back to the nightly report. Sorted by comparing, 10 million orders take about 233 million comparisons, and no comparison sort can make that ten times fewer. But look at what the report sorts by. If it's the order's status, one of 5 values (new, paid, packed, shipped, delivered), you don't need to compare at all: one pass counts how many orders have each status, and a second writes them out in status order. About 10 million steps each pass, against 233 million comparisons, and it grows as O(n). The speed-up was there, in the data, not in a cleverer comparison.
In your textbook this is stated as "comparison sorting is Ω(n log n)", read "big omega of n log n": the work is at least that much (the lesson In Your Textbook: Big-O, Big-Θ and Big-Ω explains the symbol). The tree of yes-or-no questions is called a decision tree, and counting sort and its cousin, radix sort, are the usual examples of sorts that go under the limit.
The speed-limit card
| What | Growth | The everyday reason |
|---|---|---|
| Orders of n items | n! | n choices, then n − 1, down to 1 |
| Comparisons any comparison sort needs, worst case | at least about n log n | each yes-or-no question rules out at most half the orders |
| Merge sort, any list | O(n log n) | it already reaches the limit |
| Counting sort, whole numbers 0 to k | O(n + k) | it counts instead of comparing |
Check yourself
2 questions to try on the lesson page.
So what
O(n log n) is the speed limit for sorting by comparing, so when you see a sort that's O(n log n), it's as good as comparing gets; look for savings elsewhere. When the keys are a few values or small whole numbers, though, you're allowed to break the limit by counting instead of comparing.