The Limits of Sorting

Putting things in order is one of the first things any computer does. Your contacts, your photos by date, search results by relevance — under all of it sits a sort. It feels like a solved, boring problem.

But here is a strange question: how fast can sorting possibly be? Clever people have invented dozens of sorting algorithms. Could someone, tomorrow, invent one so clever it sorts a million items in a few hundred steps?

For any algorithm that works by comparing pairs of items — "is A before B?" — the answer is a flat no. There is a wall at roughly n log n comparisons, and no amount of cleverness gets you past it. The remarkable part is that we don't just believe this — we can prove it, by counting.

Below is a small shuffled list. Verifying it is sorted is easy — one left-to-right scan, $n-1$ comparisons. Producing the sorted order is where the cost lives. Run each sorter and watch its comparison counter.

<p class="hint">{{hint}}</p>
<div class="row">
  <label>{{size_label}}
    <input id="size" type="range" min="4" max="32" value="10">
    <span id="sizeval">10</span>
  </label>
  <button id="shuffle" type="button" class="ghost">{{new_shuffle}}</button>
</div>
<div id="list" class="list"></div>
<div class="btns">
  <button id="verify" type="button">{{btn_verify}}</button>
  <button id="bubble" type="button">{{btn_bubble}}</button>
  <button id="merge" type="button">{{btn_merge}}</button>
</div>
<div class="stats">
  <div class="stat"><span class="k">{{stat_verify}}</span><span id="vcount" class="v">&ndash;</span></div>
  <div class="stat"><span class="k">{{stat_bubble}}</span><span id="bcount" class="v">&ndash;</span></div>
  <div class="stat"><span class="k">{{stat_merge}}</span><span id="mcount" class="v">&ndash;</span></div>
  <div class="stat"><span class="k">{{stat_wall}}</span><span id="wall" class="v">&ndash;</span></div>
</div>
<div id="msg" class="status"></div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
.row { display: flex; align-items: center; gap: 1rem; flex-wrap: wrap; margin: .3rem 0 .6rem; font-size: .9rem; }
.row input[type=range] { vertical-align: middle; }
.list { display: flex; gap: 3px; align-items: flex-end; height: 90px; margin: .3rem 0 .7rem; }
.bar { flex: 1; background: #1d3557; border-radius: 3px 3px 0 0; min-width: 4px; }
.bar.hot { background: #e63946; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; margin-bottom: .7rem; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
.stats { display: grid; grid-template-columns: 1fr 1fr; gap: .5rem; }
.stat { display: flex; justify-content: space-between; background: #e8eef3; border: 1px solid #cdd9e3;
        border-radius: 8px; padding: .45rem .7rem; }
.stat .k { color: #1d3557; font-size: .85rem; }
.stat .v { font: 700 15px ui-monospace, monospace; color: #0a2540; }
.status { font-size: .95rem; font-weight: 600; margin: .6rem 0 0; min-height: 1.3em; }
.status.ok { color: #0a7d33; }
.status.bad { color: #c92f3c; }

// Code not found

Bubble sort wastes effort — it pays about $n^2/2$ comparisons. Merge sort is disciplined and pays about $n \log n$. Push the size up and watch the gap explode: the smart algorithm hugs the wall, the naive one races away from it. No comparison sort ever drops below that merge-sort line — that floor is the whole story.

Here is the proof, and it is beautifully simple.

• Model every comparison sort as a decision tree. Each internal node asks one yes/no question — "is item i before item j?" — and branches two ways. The algorithm runs from the root down to a leaf, and each leaf must announce one final ordering.
• Count the outcomes. A list of n distinct items has $n!$ possible orderings, and the algorithm must be able to output every one of them. So the tree needs at least $n!$ leaves.
• A binary tree of height h has at most $2^h$ leaves. To fit $n!$ leaves we need $2^h \ge n!$, so the height — the worst-case number of comparisons — is at least $\log_{2}(n!)$.
• Stirling's approximation gives $\log_2(n!) \approx$ $n \log_2 n$. That is the theorem: every comparison sort makes $\Omega(n \log n)$ comparisons in the worst case. The same counting is an information argument — you need $n \log n$ bits to single out one ordering from $n!$.

The flip side is just as satisfying: this bound is tight. Merge sort (John von Neumann, 1945) and heapsort both run in $O(n \log n)$, so they are asymptotically optimal — they sit right on the wall. You cannot beat $n \log n$ by comparing, but you don't need to: we already match it.

The one escape hatch is to stop comparing. If you know the keys are small integers, counting sort and radix sort read the keys directly and run in $O(n)$ — they dodge the bound by never asking "is A before B?" at all. That is the same flavor of move as in P vs NP: change the model, change what's possible.

A proven lower bound is a gift: it tells engineers when to stop optimizing and when to change the rules.

• Standard libraries: the sort in Python, Java, C++ and Rust is a comparison sort tuned to the n log n bound (Timsort, introsort). Nobody hunts for a faster general comparison sort — the theorem says there isn't one.
• Databases and big data: external merge sort moves terabytes between disk and memory; knowing the comparison floor tells you the win must come from fewer passes and better I/O, not a magical algorithm.
• When to drop comparisons: sorting fixed-width integers, dates or short strings? Radix and counting sort beat the bound — used in graphics, networking and string indexing.
• The proof technique travels: the decision-tree counting argument is a template for proving other lower bounds, the rare cases where we can say "no algorithm can do better." It is a cousin of the reasoning behind data compression limits.

Sorting looks like the most ordinary task in computing, yet it hides one of the field's most elegant truths. Count the possible orderings, count the leaves a decision tree can have, and a wall appears all on its own: no comparison sort beats $\Omega(n \log n)$. Merge sort and heapsort already stand on that wall.

It is a rare and clarifying kind of knowledge. Most of the time we can't prove a problem is hard — see P vs NP, still open after fifty years. Sorting is the opposite: we know exactly how hard it is, why, and that we've already done as well as comparisons allow. The only way forward is to stop comparing.