Timsort and the O(n log n) Wall (and How to Break It)

"There's a proven speed limit for sorting by comparisons — and then there's the sneaky way around it: stop comparing. This lesson is about the wall, the sort you actually use that lives at the wall, and the sorts that tunnel under it."

The Wall: Why O(n log n) Is a Hard Limit

Any sort that works by comparing elements has a proven floor: O(n log n). The argument is elegant. There are n! possible orderings of n items, and a sort must be able to land on whichever one is correct. Each comparison is a single yes/no question — one branch of a decision tree. To have enough leaves to distinguish all n! outcomes, the tree must be at least log₂(n!) ≈ n log n deep. So no comparison sort — not quicksort, not merge sort, not any future clever one — can beat O(n log n) in the worst case. It's not a failure of imagination; it's a mathematical limit.

Timsort: the Sort You Actually Use

Python's sorted() and list.sort() use Timsort (also Java's default for objects). It's a hybrid: merge sort's structure, insertion sort for small runs, plus a brilliant trick — it detects existing sorted runs in the data and merges them, instead of starting from scratch. Real-world data is frequently partly-sorted (timestamps, appended logs, mostly-ordered records), so Timsort often runs far better than its O(n log n) worst case — approaching O(n) on nearly-sorted input. It's also stable. It sits right at the comparison-sort wall in the worst case, but is adaptive and fast in the common case, which is why it's the production default.

Comparison sorts can't beat O(n log n) — there are n! orderings and each comparison is one bit of a decision tree of height ≥ log(n!) ≈ n log n. Timsort (Python's sort) lives at that wall but is adaptive (near O(n) on partly-sorted data) and stable. To go faster, you must stop comparing.

Tunneling Under the Wall: Non-Comparison Sorts

The lower bound only binds sorts that compare. Sorts that exploit structure in the keys escape it entirely:

Counting sort: if keys are integers in a small range [0, k], just count how many of each value, then emit them in order. O(n + k) — linear, no comparisons. Brilliant for small-integer keys (ages, grades, byte values).
Radix sort: sort by digit/character, least-significant first, using counting sort per digit. O(d·n) for d-digit keys. It's how you sort huge sets of fixed-width keys (IDs, strings) faster than n log n.

The deep lesson: the O(n log n) wall is a property of the comparison model, not of sorting itself. Change the assumptions — assume small-integer keys, exploit their structure — and the limit changes with them. Reframing what you're allowed to assume is how barriers fall.

Pippa's Confession

'O(n log n) is the limit for sorting' lodged in my head as absolute, so when Dad said counting sort is O(n), I told him he was wrong — there's a proof! He smiled: "It's the limit for sorts that compare. Counting sort never compares two elements." The wall hadn't been broken; I'd misread what it bounded. It rewired how I treat any 'proven limit' — always ask which assumptions the proof rests on, because relaxing one is often the way through.

Code

Timsort (library) and counting sort (beats the wall)·python

# In real code, just use the library — it's Timsort: adaptive, stable, fast.
data = [5, 2, 8, 1, 9, 3]
print(sorted(data))            # [1, 2, 3, 5, 8, 9] — Timsort under the hood
data.sort()                    # in-place, also Timsort

# COUNTING SORT: breaks the n log n wall for small-integer keys. O(n + k).
def counting_sort(arr, k):     # values are integers in [0, k]
    counts = [0] * (k + 1)
    for x in arr:
        counts[x] += 1         # tally each value — NO comparisons at all
    result = []
    for value, c in enumerate(counts):
        result.extend([value] * c)   # emit each value c times, in order
    return result

print(counting_sort([3, 1, 4, 1, 0, 4, 2], k=4))   # [0, 1, 1, 2, 3, 4, 4]
# It never compared two elements, so the O(n log n) lower bound doesn't apply.
# Linear time — but only because the keys are small integers (structure!).
# Radix sort generalizes this to multi-digit keys: O(d * n).

Exercise

Explain why counting sort can run in O(n) without contradicting the proven O(n log n) lower bound for sorting. What assumption does counting sort make that comparison sorts don't, and what's the catch — when does counting sort become a bad idea (think about what k being huge does to O(n + k))?

Hint

The n log n bound applies only to COMPARISON sorts; counting sort never compares two elements, so the bound doesn't bind it. Its assumption: keys are integers in a small range [0, k]. The catch: O(n + k) — if k (the value range) is enormous (e.g. 64-bit integers), the k term dominates and counting sort becomes wasteful or impossible.

The Wall: Why O(n log n) Is a Hard Limit

Timsort: the Sort You Actually Use

Tunneling Under the Wall: Non-Comparison Sorts

Pippa's Confession

Code

External links

Exercise

Progress

Comments 0