Introduction

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.

Try It: Count the Comparisons

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

<p class="hint">The same shuffled list, two algorithms. <b>Verifying</b> it is sorted is one cheap left-to-right scan. <b>Producing</b> the order is where the cost lives — and bubble sort pays about n&sup2;/2 comparisons while merge sort hugs the n&middot;log&#8322;n wall.</p>
<div class="row">
  <label>List size:
    <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">Verify sorted</button>
  <button id="bubble" type="button">Run bubble sort</button>
  <button id="merge" type="button">Run merge sort</button>
</div>
<div class="stats">
  <div class="stat"><span class="k">Verify (scan)</span><span id="vcount" class="v">&ndash;</span></div>
  <div class="stat"><span class="k">Bubble sort</span><span id="bcount" class="v">&ndash;</span></div>
  <div class="stat"><span class="k">Merge sort</span><span id="mcount" class="v">&ndash;</span></div>
  <div class="stat"><span class="k">Wall &asymp; n&middot;log&#8322;n</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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// The n log n lower bound made visible: bubble sort (~n^2/2 comparisons) vs
// merge sort (~n log2 n), both counting every "is a < b?" question. Verifying a
// sorted list is only n-1 comparisons — checking is cheap, producing is not.
// No comparison sort can drop below ~log2(n!) ~ n log2 n comparisons (decision-tree bound).
let arr = [];
const $ = id => document.getElementById(id);

function shuffle(n){
  arr = Array.from({length:n}, (_,i)=>i+1);
  for(let i=n-1;i>0;i--){ const j=Math.floor(Math.random()*(i+1)); [arr[i],arr[j]]=[arr[j],arr[i]]; }
  render(); clearStats();
}
function render(hot){
  const box=$('list'); box.innerHTML=''; const max=arr.length||1;
  arr.forEach((v,i)=>{ const b=document.createElement('div');
    b.className='bar'+(hot&&hot.includes(i)?' hot':''); b.style.height=(8+82*v/max)+'px'; box.appendChild(b); });
}
function clearStats(){ $('vcount').textContent='–'; $('bcount').textContent='–';
  $('mcount').textContent='–'; $('wall').textContent='–'; setMsg('',''); }
function setMsg(t,cls){ const m=$('msg'); m.textContent=t; m.className='status '+cls; }

// Verify: a single scan, n-1 comparisons. Cheap.
function verify(){
  let cmp=0, ok=true;
  for(let i=1;i<arr.length;i++){ cmp++; if(arr[i-1]>arr[i]){ ok=false; break; } }
  $('vcount').textContent=cmp;
  setMsg(ok ? fmt('✓ Sorted — verified in %cmp% comparisons (one scan).', { cmp: cmp })
            : fmt('✗ Not sorted — a scan caught it in %cmp% comparisons.', { cmp: cmp }), ok?'ok':'bad');
}

// Bubble sort: counts comparisons, returns count. ~n^2/2 in the worst case.
function bubbleCount(a){
  a=a.slice(); let cmp=0; const n=a.length;
  for(let i=0;i<n-1;i++) for(let j=0;j<n-1-i;j++){ cmp++; if(a[j]>a[j+1]){ const t=a[j]; a[j]=a[j+1]; a[j+1]=t; } }
  return {cmp, sorted:a};
}
// Merge sort: counts comparisons, returns count. ~n log2 n.
function mergeCount(a){
  let cmp=0;
  function ms(x){
    if(x.length<=1) return x;
    const mid=x.length>>1, L=ms(x.slice(0,mid)), R=ms(x.slice(mid)), out=[];
    let i=0,j=0;
    while(i<L.length && j<R.length){ cmp++; if(L[i]<=R[j]) out.push(L[i++]); else out.push(R[j++]); }
    while(i<L.length) out.push(L[i++]);
    while(j<R.length) out.push(R[j++]);
    return out;
  }
  const sorted=ms(a); return {cmp, sorted};
}

function runBubble(){ const r=bubbleCount(arr); arr=r.sorted; render();
  $('bcount').textContent=r.cmp; showWall(); setMsg(fmt('Bubble sort finished: %cmp% comparisons.', { cmp: r.cmp }),''); }
function runMerge(){ const r=mergeCount(arr); arr=r.sorted; render();
  $('mcount').textContent=r.cmp; showWall(); setMsg(fmt('Merge sort finished: %cmp% comparisons.', { cmp: r.cmp }),''); }
function showWall(){ const n=arr.length; const w=Math.ceil(n*Math.log2(Math.max(n,1)));
  $('wall').textContent='~'+w; }

$('size').addEventListener('input', e=>{ $('sizeval').textContent=e.target.value; shuffle(+e.target.value); });
$('shuffle').addEventListener('click', ()=>shuffle(+$('size').value));
$('verify').addEventListener('click', verify);
$('bubble').addEventListener('click', runBubble);
$('merge').addEventListener('click', runMerge);
shuffle(10);
Result
Console

Bubble sort wastes effort — it pays about n2/2n^2/2 comparisons. Merge sort is disciplined and pays about nlog⁡nn \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.

The Real Complexity

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!n! possible orderings, and the algorithm must be able to output every one of them. So the tree needs at least n!n! leaves.
  • A binary tree of height h has at most 2h2^h leaves. To fit n!n! leaves we need 2h≥n!2^h \ge n!, so the height — the worst-case number of comparisons — is at least log⁡2(n!)\log_{2}(n!).
  • Stirling's approximation gives log⁡2(n!)≈\log_2(n!) \approx nlog⁡2nn \log_2 n. That is the theorem: every comparison sort makes Ω(nlog⁡n)\Omega(n \log n) comparisons in the worst case. The same counting is an information argument — you need nlog⁡nn \log n bits to single out one ordering from n!n!.

The flip side is just as satisfying: this bound is tight. Merge sort (John von Neumann, 1945) and heapsort both run in O(nlog⁡n)O(n \log n), so they are asymptotically optimal — they sit right on the wall. You cannot beat nlog⁡nn \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)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.

Where It Matters

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.

Conclusion

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 Ω(nlog⁡n)\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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/sorting-lower-bound/Content licensed under CC BY-NC 4.0.