Sorting Lower BoundThe comparison sort lower bound

01Why it exists

Reach for it when you see:Can this be any faster, is O(n log n) the limit, decision trees, log₂(n!), a problem that demands O(n) yet looks like it needs sorting, comparisons only, information content, lower-bound arguments.

02The core idea

A comparison sort is a sorting algorithm whose only way of learning about its input is to ask which of two elements is larger: bubble, insertion, merge, quick and heap sort all qualify. However such an algorithm is written, for a fixed n it can be drawn as a decision tree: each internal node is one comparison, "a < b?", and the answer decides whether you go left or right; each leaf is one of the orderings the algorithm can output. Running it on an input means walking from the root down to some leaf, and the number of comparisons equals the length of that path, so the worst-case comparison count is the height of the tree.

The proof is just counting leaves. n distinct elements have n! orderings, and each one needs a different rearrangement to become sorted, so a correct algorithm must have at least n! reachable leaves. Otherwise two different inputs would end at the same leaf and get the same rearrangement, and at least one of them would come out wrong. A binary tree of height h has at most 2ʰ leaves, so 2ʰ ≥ n!, which is h ≥ log₂(n!). Any comparison sort therefore needs at least ⌈log₂ n!⌉ comparisons in the worst case: ⌈log₂ 6⌉ = 3 for n = 3, and ⌈log₂ 24⌉ = 5 for n = 4.

How big is that quantity? On one side n! ≤ nⁿ, so log₂ n! ≤ n log₂ n. On the other, n! has at least n/2 factors that are no smaller than n/2, so n! ≥ (n/2)^(n/2) and log₂ n! ≥ (n/2) log₂(n/2). Squeezing from both sides gives log₂(n!) = Θ(n log n), and Stirling's approximation sharpens it to n log₂ n − 1.443n + O(log n). So the worst case of a comparison sort is Ω(n log n), which makes the worst-case O(n log n) of merge sort and heap sort asymptotically optimal. The average case does not escape either: in a binary tree with n! leaves the average leaf depth is also at least log₂(n!), so quicksort's average O(n log n) is optimal as well.

The bound is often misread. First, it only governs the comparison model: counting sort uses values as array indices and radix sort reads the digits of a number, and one such operation reveals far more than a single yes-or-no answer, so O(n + k) and O(d·n) are no contradiction — they simply require keys that are small integers or of fixed width. Second, it talks about the worst of all n! inputs: when the input is known to be nearly sorted, far fewer orderings are possible, and insertion sort's O(n + number of inversions) is not restricted by this bound. Third, ⌈log₂ n!⌉ is not always achievable: for n = 5 the bound is 7, ordinary merge and binary insertion sorts need 8 in the worst case, and only the carefully designed merge insertion sort reaches 7 — while n = 12 has been proved to need 30, one more than the bound. The same "count the possible answers" argument works on other problems: searching a sorted array has n + 1 possible outcomes, which is exactly why binary search's ⌈log₂(n+1)⌉ comparisons are optimal too.

03The algorithm

1. 1Confirm the model of computation: can the algorithm only obtain information by comparing two elements? Once hashing, indexing or bit operations are in play, this bound no longer applies.
2. 2Count how many possible answers there are: sorting n distinct elements has n!, searching a sorted array has n + 1.
3. 3Draw any such algorithm as a decision tree: every comparison branches two ways, a tree of height h holds at most 2ʰ leaves, and every answer needs a leaf of its own.
4. 4From 2ʰ ≥ number of answers you get h ≥ ⌈log₂ number of answers⌉; for sorting that is ⌈log₂ n!⌉ = Ω(n log n).
5. 5When you need it faster, the only move is to change the premise: counting or radix sort when the keys are small integers, an adaptive insertion sort when the input is nearly ordered, and no full sort at all when you only need the k-th smallest or the top K.

04Interactive demo

Pick n = 2, 3 or 4. The four numbers along the top are n!, log₂ n!, the fewest comparisons the worst case can need, and n log₂ n for reference. The row of boxes below shows how many leaves a binary tree of height h can hold: grey is too few, and blue marks the first height that fits all n! of them. For n = 3 an actual decision tree is drawn, so choosing an input shows how many comparisons it makes along the amber path and which leaf it lands on: [5, 2, 9] takes only 2 comparisons and [5, 9, 2] takes 3, but no input ever exceeds 3. The table at the bottom pushes n up to a million, where the ratio of log₂ n! to n log₂ n creeps toward 1.

05Code

The code turns the proof into numbers you can run: lower_bound computes ⌈log₂ n!⌉ exactly with integer arithmetic, and two sorts that may only compare through less(x, y) are then run over all n! permutations of n elements with their comparisons counted. The table shows two things: no algorithm ever drops below the bound, and from n = 5 onward the familiar algorithms sit one or two comparisons above it — the bound is an "at least", not an "exactly".

import math
from itertools import permutations


def lower_bound(n):
    """Any comparison sort needs at least ⌈log₂ n!⌉ comparisons in the worst case (integer maths, so no float error)"""
    return (math.factorial(n) - 1).bit_length()   # for m ≥ 1, (m − 1).bit_length() = ⌈log₂ m⌉


# Two sorts that may only ask less(x, y), so the comparisons can actually be counted
def merge_sort(a, less):
    if len(a) <= 1:
        return a
    mid = len(a) // 2
    left, right = merge_sort(a[:mid], less), merge_sort(a[mid:], less)
    out, i, j = [], 0, 0
    while i < len(left) and j < len(right):
        if less(right[j], left[i]):
            out.append(right[j]); j += 1
        else:
            out.append(left[i]); i += 1
    return out + left[i:] + right[j:]


def binary_insertion_sort(a, less):
    out = []
    for x in a:
        lo, hi = 0, len(out)
        while lo < hi:                             # binary search for the slot inside the sorted out
            mid = (lo + hi) // 2
            if less(x, out[mid]):
                hi = mid
            else:
                lo = mid + 1
        out.insert(lo, x)
    return out


def worst_comparisons(sort, n):
    """Run all n! permutations of n distinct elements; return the largest comparison count"""
    worst = 0
    for perm in permutations(range(n)):
        count = 0

        def less(x, y):
            nonlocal count
            count += 1
            return x < y

        sort(list(perm), less)
        worst = max(worst, count)
    return worst


if __name__ == "__main__":
    for n in range(2, 9):
        print(n, lower_bound(n), worst_comparisons(merge_sort, n),
              worst_comparisons(binary_insertion_sort, n))
    # n  bound  merge  binary insertion
    # 2   1    1     1
    # 3   3    3     3
    # 4   5    5     5
    # 5   7    8     8      ← the bound of 7 is reachable (merge insertion); neither of these two gets there
    # 6  10   11    11
    # 7  13   14    14
    # 8  16   17    17
    n = 10**6                                      # estimate log₂ n! with lgamma and compare it against n log₂ n
    print(round(math.lgamma(n + 1) / math.log(2) / (n * math.log2(n)), 3))   # 0.928

06Practice

• LeetCode 217Contains Duplicate (sorting at O(n log n) versus hashing at O(n), which is outside the comparison model)Easy
• LeetCode 278First Bad Version (n possible answers, so at least log₂ n queries)Easy
• LeetCode 128Longest Consecutive Sequence (O(n) required, so sorting first is out)Medium
• LeetCode 164Maximum Gap (linear time required; bucket with the pigeonhole principle)Medium
• LeetCode 41First Missing Positive (use values as indices and leave the comparison model)Hard