What this calculator does
There is a hard floor on sorting by comparison, and it comes from counting rather than from any algorithm. A list of n items has n factorial possible orderings, and each comparison has two outcomes, so k comparisons can distinguish at most 2^k arrangements. To separate all n factorial of them you need at least log base 2 of n factorial comparisons, rounded up.
For a thousand items that floor is 8,530 comparisons. Merge sort spends 8,977, which is within about five per cent of a bound that no comparison sort can ever beat. That is the useful thing this calculation tells you: the good algorithms are already close to optimal, and the room left is small.
The formula
The floor is ceil(log₂ n!). Merge sort's worst case is n·ceil(log₂ n) − 2^ceil(log₂ n) + 1. Binary insertion sort inserts each item by binary search, costing the sum of ceil(log₂ k) over k, which is close to the floor but wastes the moves. Insertion sort's worst case is n(n−1)/2, every pair compared. Quicksort averages about 2n ln n, which is roughly 1.39 times the floor.
| Term | Meaning |
|---|---|
| Comparison sort | A sort that only ever asks whether one item is before another. Counting sorts and radix sorts are not comparison sorts and are not bound by this floor. |
| Information-theoretic minimum | ceil(log₂ n!). A lower bound on the worst case, not always achievable. |
| Worst case | The most comparisons the method can be forced into by an adversarial input. |
| Average case | What happens on a random input. Quicksort's worst case is quadratic, but it is rare. |
The inputs explained
| Field | What to enter |
|---|---|
| Items to sort | How many items are being sorted. Capped at 100,000 because the factorial logarithm is summed term by term. |
When to use it
Judging whether an algorithm is good
Compare any method against the floor. Merge sort sits about five per cent above it at a thousand items and the gap narrows as n grows. Insertion sort at the same size spends 499,500 comparisons, nearly sixty times the floor, which is why it is only used on short lists.
Understanding why small sorts are special
At five items the floor is 7 and merge sort spends 8. That one comparison is worth chasing when the sort is a base case being run billions of times, which is exactly where AlphaDev found its improvements.
Deciding on a cutoff for hybrid sorts
Real library sorts switch to insertion sort below some size, because its quadratic comparison count is still small when n is tiny and it has almost no overhead. Comparing the columns at sizes under about 20 shows why that trade works.
Worked examples
Every figure in the tables below is produced by this page’s own calculator at build time, so the numbers and the tool always agree. Select any row to load that scenario.
How close to the floor do real sorts get?
The list length rises by powers of ten.
| Items | Information-theoretic minimum | Merge sort, worst case | Insertion sort, worst case |
|---|---|---|---|
| 10 | 22 | 25 | 45 |
| 100 | 525 | 573 | 4,950 |
| 1,000 | 8,530 | 8,977 | 499,500 |
| 10,000 | 118,459 | 123,617 | 49,995,000 |
| 100,000 | 1,516,705 | 1,568,929 | 4,999,950,000 |
What happens on very short lists?
Small n, where the rounding in the floor is doing real work.
| Items | Information-theoretic minimum | Merge sort, worst case | Binary insertion sort, worst case |
|---|---|---|---|
| 2 | 1 | 1 | 1 |
| 3 | 3 | 3 | 3 |
| 4 | 5 | 5 | 5 |
| 5 | 7 | 8 | 8 |
| 6 | 10 | 11 | 11 |
| 8 | 16 | 17 | 17 |
| 12 | 29 | 33 | 33 |
Questions
Can anything beat the information-theoretic floor?
Not by comparing. Counting sort, radix sort and bucket sort can go faster because they look at the values themselves rather than only comparing pairs, so the argument does not apply to them.
Is the floor always achievable?
No. For twelve items the floor is 29 comparisons but 30 are genuinely required, and the same happens at thirteen. The bound is a lower limit, not a promise.
Why does merge sort look worse than binary insertion sort?
On comparisons alone binary insertion sort is close to the floor, but inserting an item means shifting everything after it, so it does many more data moves. Comparisons are only one of the costs.
What did AlphaDev actually improve?
Not the comparison counts, but the machine instructions. It found shorter assembly sequences for sorting three, four and five elements, which went into the LLVM standard C++ library in 2023.
Why is quicksort used if merge sort needs fewer comparisons?
Because quicksort sorts in place with excellent memory locality, and comparisons are rarely the bottleneck on modern hardware. Its average is about 39 per cent above the floor, which is a price worth paying for the cache behaviour.
To sort an actual list there is the sort numbers calculator, and for the counting behind n factorial see permutations and combinations. How the small cases were improved is in the piece on AlphaDev.