Sorting and Searching: The n log n Lower Bound, and How to Beat It Legally

Binary search, written so it terminates

Nearly every bug here is the same bug: the loop condition and the update disagree about whether the endpoint is inside the search space. Fix a convention — half-open \([lo, hi)\), so \(hi\) is one past the last candidate — and state the invariant: the answer, if it exists, is in \([lo, hi)\).

def lower_bound(a, target):
    """Leftmost index i with a[i] >= target, for sorted a. Theta(log n).
    Invariant: the answer always lies in the half-open interval [lo, hi)."""
    lo, hi = 0, len(a)
    while lo < hi:
        mid = (lo + hi) // 2       # lo <= mid < hi, so the interval always shrinks
        if a[mid] < target:
            lo = mid + 1           # a[mid] is excluded: it is too small
        else:
            hi = mid               # a[mid] is still a candidate, hence hi = mid
    return lo                      # lo == hi: the interval is empty

a = [1, 3, 3, 5, 8]
print(lower_bound(a, 3))   # 1  -- leftmost of the two 3s
print(lower_bound(a, 4))   # 3  -- insertion point
print(lower_bound(a, 9))   # 5  -- past the end

Three things make it correct. mid satisfies \(lo \le mid < hi\), so every branch strictly shrinks the interval and the loop must terminate. The hi = mid branch keeps mid as a candidate — pairing it with while lo <= hi would spin forever. And returning lo makes the function total: it answers “where would it go” for absent targets. Flip one comparison to a[mid] <= target for the rightmost occurrence; in production use bisect.bisect_left / bisect_right, which are this code in C.

One historical note: mid = (lo + hi) // 2 can overflow in fixed-width integer languages — the bug found in the JDK’s binarySearch after years in the library — so write lo + (hi - lo) // 2 there. Python’s integers are arbitrary precision, so it cannot happen here.

The three comparison sorts worth knowing

Merge sort splits in half, sorts each half, and merges. The recurrence \(T(n) = 2T(n/2) + \Theta(n)\) gives \(\Theta(n\log n)\) in all cases by the Master theorem. It is stable, needs \(\Theta(n)\) auxiliary space, and because it streams sequentially it is the algorithm for linked lists and for external sorting.

Quicksort partitions around a pivot and recurses on both sides. A balanced split gives the same recurrence and \(\Theta(n\log n)\); a maximally unbalanced split gives \(T(n) = T(n-1) + \Theta(n) = \Theta(n^2)\). With a fixed pivot (first or last element) the worst case is triggered by sorted input — the most common real input there is. Choosing the pivot uniformly at random makes the expected time \(\Theta(n\log n)\) for every input, because the randomness now lives in the algorithm rather than in an assumption about the data; the \(\Theta(n^2)\) case survives but no adversary can force it. It sorts in place with \(\Theta(\log n)\) expected stack depth, and its constant is small enough that it beats merge sort in practice.

Heapsort builds a heap in \(\Theta(n)\) and extracts the maximum \(n\) times: \(\Theta(n\log n)\) worst case, in place, unstable, and cache-hostile. Its real use is as a safety net — introsort runs quicksort but switches to heapsort once recursion depth exceeds \(\approx 2\log_2 n\), keeping quicksort’s average speed with a hard \(O(n\log n)\) bound.

Why Ω(n log n) is a theorem

Any algorithm that only compares elements is a decision tree: internal nodes are comparisons, each with two outcomes, and each leaf is one permutation the algorithm can output. To sort correctly it must be able to produce all \(n!\) orderings, so the tree has at least \(n!\) leaves. A binary tree of height \(h\) has at most \(2^h\) leaves, so \(2^h \ge n!\) and

using that the top half of the factors in \(n!\) are each at least \(n/2\). The height is the worst-case number of comparisons, so no comparison sort can do better. This is a statement about all possible algorithms, which is why it is \(\Omega\) and not \(O\).

Stability, and when it matters

A stable sort preserves the relative order of equal keys. This is what lets you sort by several keys with repeated passes: sort by the secondary key first, then by the primary, and the earlier order survives inside ties.

rows = [("bob", 2), ("amy", 1), ("cal", 2), ("dee", 1)]
rows.sort(key=lambda r: r[0])          # secondary key: name
rows.sort(key=lambda r: r[1])          # primary key: group
print(rows)   # [('amy', 1), ('dee', 1), ('bob', 2), ('cal', 2)]

Python’s list.sort and sorted are stable, guaranteed by the language reference; they run Timsort, which exploits pre-existing runs and is \(\Theta(n)\) on already-sorted input. numpy.sort defaults to an introsort-style quicksort, which is not stable — pass kind="stable" if you rely on it.

Beating the bound legally

The lower bound applies only to comparison-based algorithms. Sorts that read the keys’ structure instead escape it, at the cost of a precondition:

• Counting sort: integer keys in a known range \([0, k)\). \(\Theta(n+k)\) time and space, stable. Useless when \(k \gg n\) — sorting 64-bit integers this way needs \(2^{64}\) counters.
• Radix sort: fixed-width keys sorted digit by digit with a stable counting sort per digit, \(\Theta(d(n+k))\) for \(d\) digits. Stability per pass is what makes it correct.
• Bucket sort: distribute into buckets, sort each. Linear expected time under the assumption that keys are uniformly distributed — an assumption about your data, not a guarantee.

References

1. Hoare, C. A. R. Quicksort. The Computer Journal 5(1), 10–16, 1962.
2. Knuth, D. E. The Art of Computer Programming, Vol. 3: Sorting and Searching, 2nd ed. Addison-Wesley, 1998 — §5.3.1 for the comparison lower bound, §6.2.1 for binary search.
3. Musser, D. R. Introspective sorting and selection algorithms. Software: Practice and Experience 27(8), 983–993, 1997 — introsort.
4. Bentley, J. L., & McIlroy, M. D. Engineering a sort function. Software: Practice and Experience 23(11), 1249–1265, 1993.
5. Peters, T. listsort.txt — Timsort, as implemented in CPython.
6. Python Software Foundation. Sorting Techniques and bisect.
7. NumPy developers. numpy.sort — sort kinds and their stability.