6.21 Lower Bounds for Sorting

Lower bounds describe what no algorithm can beat under a given model. For sorting, the standard model is comparison-based sorting, where the algorithm learns order only by comparing elements. In this model, any algorithm must use at least on the order of ( n \log n ) comparisons in the worst case.

Problem

You want to understand the inherent cost of sorting and why many algorithms converge to ( O(n \log n) ) time.

Decision Tree Model

A comparison-based sorting algorithm can be represented as a decision tree.

• Each internal node is a comparison such as A[i] ≤ A[j]
• Each branch corresponds to the result of that comparison
• Each leaf corresponds to a final permutation (a possible sorted outcome)

To sort correctly, the algorithm must distinguish between all possible input permutations.

For n distinct elements, there are:

n!

possible permutations.

Therefore, the decision tree must have at least n! leaves.

Depth of the Tree

A binary decision tree of depth d has at most:

2^d

leaves.

To distinguish n! permutations:

2^d ≥ n!

Taking logarithms:

d ≥ log2(n!)

Using Stirling’s approximation:

log2(n!) ≈ n log2(n) - n

So any comparison-based sorting algorithm must perform at least:

Ω(n log n)

comparisons in the worst case.

Interpretation

This lower bound applies to all comparison-based algorithms:

• merge sort
• heap sort
• quick sort
• balanced tree sorting

Even if implementations differ, they cannot asymptotically beat this bound in the worst case under the comparison model.

Tightness

There exist algorithms that match the lower bound:

merge sort → O(n log n)
heap sort  → O(n log n)

This means the lower bound is tight. It is both a lower bound and an achievable upper bound.

Average Case

The same lower bound applies to average-case comparison count under reasonable assumptions.

No comparison-based algorithm can achieve:

o(n log n)

on average for arbitrary inputs.

When Linear Time is Possible

The lower bound applies only to comparison-based sorting.

If additional structure is available, the bound does not apply.

Examples:

counting sort → O(n + k)
radix sort    → O(d(n + b))
bucket sort   → O(n) expected

These algorithms avoid comparisons by exploiting:

• bounded integer ranges
• digit decomposition
• known distributions

They trade generality for speed.

Information-Theoretic View

Sorting extracts information about the order of elements.

Each comparison gives at most one bit of information. To determine one permutation among n!, the algorithm must gather enough bits to identify it.

The number of bits needed is:

log2(n!)

This matches the decision tree argument and leads to the same lower bound.

Implications

• You cannot design a general-purpose comparison sort faster than ( O(n \log n) ) in the worst case
• Optimization focuses on constants, memory access, and adaptiveness
• Hybrid algorithms aim to approach the lower bound while handling practical inputs efficiently

Beyond Worst Case

Lower bounds can change under different assumptions:

For example, in external memory, the cost is measured in block transfers rather than comparisons.

Common Misconceptions

A frequent misunderstanding is believing that a clever comparison strategy can beat ( n \log n ). The lower bound proves this impossible in the general case.

Another mistake is assuming that quick sort is faster because it “usually” runs in linear time. Its average complexity is still ( O(n \log n) ), even if constants are small.

A third mistake is applying counting sort without checking constraints. Linear-time sorting requires specific assumptions about keys.

Takeaway

Sorting has a fundamental lower bound under comparisons. The ( O(n \log n) ) complexity is not accidental. It reflects the minimum information required to determine the correct order among all possible permutations.