Chalkboard diagram: a binary decision tree with comparison nodes and permutation leaves, proving the n log n lower bound for comparison sorts Algorithms & Data Structures • Sensei Learning System

Comparison Sorts: Why the Lower Bound Is n log n

The cleanest “you cannot do better than this” proof in all of algorithms — one decision tree, one factorial, and you’re done.

💡 Core Concept

A comparison sort learns about the input only by asking pairwise questions — “is a less than b?” — and never looks inside the keys. Model any deterministic comparison sort as a binary decision tree: every question is a branch, every complete run ends at a leaf holding the discovered order.

There are n! possible orders of n distinct keys, so the tree needs at least n! leaves — and a binary tree of height h has at most 2h leaves. That single fact forces the bound:

worst-case comparisons ≥ ⌈log₂(n!)⌉ ≈ n log₂ n

No comparison sort — no matter how clever — can guarantee worst-case Ω(n log n) comparisons. This is not a limitation of known algorithms; it is a law of the model.

🧱 Key Components

Decision-tree model

Each internal node is one comparison “a < b?”, each branch a yes/no answer, each leaf a fully determined input order.

n! leaves required

Every one of the n! permutations must end at its own leaf: two inputs reaching the same leaf got identical answers, so they’d be sorted identically — impossible.

Stirling’s squeeze

log₂(n!) = n log₂ n − 1.44n + O(log n), so ⌈log₂(n!)⌉ grows like n log n. The factorial becomes the bound.

Tight, but not universal

Merge sort and heapsort hit O(n log n) worst-case — the bound is tight. Quicksort averages O(n log n) but degrades to O(n²) with bad pivots.

⚙️ How It Works

  1. Only questions. The algorithm may inspect keys solely via comparisons “a < b?” — nothing else counts as information.
  2. Fix the strategy. For any fixed deterministic sort, the sequence of questions it asks on any input traces a path down a binary tree — its decision tree.
  3. One leaf per order. Two inputs that reach the same leaf received identical yes/no answers, so the algorithm would output the same permutation for both. Hence each leaf serves at most one input order.
  4. Count the leaves. n distinct keys have n! possible orders → the tree needs at least n! leaves.
  5. Count the height. A binary tree of height h holds ≤ 2h leaves → h ≥ ⌈log₂(n!)⌉ ≈ n log₂ n. The worst-case input is the deepest leaf.

📑 Worked example: n = 4

Four distinct keys can arrive in 4! = 24 orders. A 4-level tree holds only 2⁴ = 16 leaves — not enough. So some input forces at least ⌈log₂ 24⌉ = 5 comparisons. No sorting trick escapes it.

⚖️ The Fine Print: What the Bound Does NOT Cover

This is a lower bound on comparison-based sorting, not on sorting in general. The model’s only information source is “a < b?” — and that constraint is exactly what non-comparison sorts dodge.

Counting sort (keys in 0…k) and radix sort use the keys’ structure — bucket indexing, digit-by-digit passes — to place items without asking pairwise questions. They run in roughly linear time (O(n + k), O(d·n)) for bounded/structured keys. That does not disprove the bound: it changes the model by adding an operation the comparison sort is not allowed.

🌐️ Real-World Applications

📦

Standard library sorts. C’s qsort, Python’s Timsort, Java’s Arrays.sort — all comparison sorts. The bound is the ceiling: O(n log n) is “as good as it gets” for arbitrary keys, which is why nobody hunts for a faster general-purpose one.

📊

Database ORDER BY and index builds. Sorting arbitrary values (strings, timestamps, composite keys) is comparison sorting; the bound sets the expected cost you’re paying when a query files away a large result set.

⚡

Picking counting/radix sorts. When keys are bounded integers — byte arrays, fixed-width IDs, scores 0–100 — you can legally leave the comparison model and get linear-ish time. Recognizing when you may is the real skill the bound teaches.

🧠

Lower-bound thinking in general. Proving an algorithm cannot be faster is worth as much as finding a fast one — it stops whole search programs (e.g. “faster than n log n general sorting?”) before they start.

✅️ Checkpoint — answer before you move on

  1. Why must a deterministic comparison sort’s decision tree have at least n! leaves? Think: what happens to two different inputs that reach the same leaf?
  2. Run the n = 4 case by hand: how many comparisons must some input require, and where does that number come from? 4! permutations, then the leaf-count rule for binary trees.
  3. Someone claims: “Counting sort runs in O(n + k), so the n log n lower bound is false.” Identify the extra operation counting sort uses that the comparison model forbids. What does a bucket index read that “a < b?” never tells you?