Non-Comparison Sorts

Three different ideas — merging, partitioning, heaping — arrived at the same bound: $\Theta(n \log n)$. This is not a coincidence. This lesson first proves why the bound cannot be surpassed, then shows how it can be surpassed by removing the proof’s assumption.

Proof of the Lower Bound

A comparison-based sorting algorithm looks not at the elements’ values but only at the outcomes of comparisons. Such an algorithm’s behavior can be drawn as a decision tree: every internal node is a comparison, every branch is one of the outcomes, every leaf is a produced permutation.

If the algorithm is correct, it must correctly sort every possible arrangement of the $n$ elements; so the tree has at least $n!$ leaves. The worst-case number of comparisons is the tree’s height, and a binary tree of height $h$ has at most $2^h$ leaves:

$$2^h \geq n! \implies h \geq \log_2(n!) = \Omega(n \log n)$$

The last equality follows from the fact that at least half of $n!$’s factors are greater than $n/2$: $n! \geq (n/2)^{n/2}$, that is, $\log_2(n!) \geq \frac{n}{2}\log_2\frac{n}{2}$.

import math

for n in (10, 100, 1_000, 10_000):
    print(n, round(math.log2(math.factorial(n))), round(n * math.log2(n)))

# 10 22 33
# 100 525 664
# 1000 8529 9966
# 10000 118458 132877

The lower bound and the upper bound are of the same order; merge sort is only a small factor away from the bound. Any improvement to be made in comparison-based sorting is limited to a constant.

The proof rests on a single assumption: the algorithm only compares. If the structure of the keys is used, the proof no longer applies.

Counting Sort

Assumption: the keys are integers between $0$ and $k-1$.

How many times each value occurs is counted, the counts are turned into a cumulative sum, and elements are written directly into their final positions.

def counting_sort(array: list[int], k: int) -> list[int]:
    """Keys are in the range 0..k-1. Cost O(n + k), stable."""
    counts = [0] * k
    for value in array:
        counts[value] += 1

    for i in range(1, k):                  # cumulative sum: end positions
        counts[i] += counts[i - 1]

    result = [0] * len(array)
    for value in reversed(array):          # going from end to start preserves stability
        counts[value] -= 1
        result[counts[value]] = value
    return result


print(counting_sort([5, 2, 9, 1, 5, 6], 10))     # [1, 2, 5, 5, 6, 9]
print(counting_sort([3, 0, 3, 0], 4))            # [0, 0, 3, 3]

Cost is $O(n + k)$, extra space is $O(n + k)$. No comparison is made; every element finds its position by arithmetic.

Traversing in reverse order is not a detail: it is exactly what provides stability. Among elements with equal keys, the one that comes last settles into the cumulative counter’s last position, and relative order is preserved. This is invisible in the numbers themselves; it becomes decisive in uses where the key is part of a larger record.

The method’s limit lies in $k$: if the value range is much larger than the element count ($k \gg n$), cost and memory are determined by $k$. Sorting 32-bit integers with counting sort would require a count array of four billion entries.

Bucket Sort

Assumption: the keys lie in a known range and are approximately uniformly distributed.

The range is divided into equal parts, every element is dropped into its own bucket, the buckets are sorted internally, and they are concatenated in order.

def bucket_sort(array: list[float], bucket_count: int) -> list[float]:
    """For values in the range 0 <= x < 1. Expected cost O(n) under uniform distribution."""
    if not array:
        return []
    buckets: list[list[float]] = [[] for _ in range(bucket_count)]
    for value in array:
        buckets[int(value * bucket_count)].append(value)

    result: list[float] = []
    for bucket in buckets:
        bucket.sort()                      # small bucket: insertion sort would work too
        result.extend(bucket)
    return result


print(bucket_sort([0.42, 0.11, 0.95, 0.47, 0.03], 5))
# [0.03, 0.11, 0.42, 0.47, 0.95]

Under uniform distribution, every bucket receives $n / \text{bucket count}$ elements on average; if the bucket count is chosen proportional to $n$, the sorts within buckets have constant cost, and the expected total is $O(n)$.

When the assumption breaks, so does the guarantee: if all the elements fall into a single bucket, cost falls back to that of the algorithm used within the bucket — typically $O(n \log n)$ or $O(n^2)$. This is an example of the “linear” claim depending on the data.

Radix Sort

Assumption: the keys are made up of a fixed number of digits.

Elements are sorted digit by digit. It starts from the least significant digit, and a stable sort is used at every digit; stability ensures the order established by the previous digits is preserved.

def radix_sort(array: list[int], base: int = 10) -> list[int]:
    """For non-negative integers. Cost O(d * (n + base))."""
    if not array:
        return []
    result = list(array)
    divisor = 1
    while max(result) // divisor > 0:
        buckets: list[list[int]] = [[] for _ in range(base)]
        for value in result:
            buckets[(value // divisor) % base].append(value)
        result = [value for bucket in buckets for value in bucket]
        divisor *= base
    return result


print(radix_sort([170, 45, 75, 90, 2, 802, 24, 66]))
# [2, 24, 45, 66, 75, 90, 170, 802]
print(radix_sort([5, 2, 9, 1, 5, 6]))
# [1, 2, 5, 5, 6, 9]

For $d$ digits and base $b$, the cost is $O(d \cdot (n + b))$. If key width is constant — fixed-width integers, fixed-length strings — this expression reduces to $O(n)$.

Variants that start from the most significant digit also exist; they are preferred for sorting text because they provide early discrimination, but they require a recursive structure.

How “Linear” Is “Linear”

All three algorithms surpass the lower bound, but not for free. An honest assessment notes three points.

Assumptions are real constraints. Counting sort needs a small integer range, bucket sort needs uniform distribution, radix sort needs a fixed-width key. A general-purpose library sort cannot make these assumptions.

Key width depends on $n$. If $n$ distinct keys are to be distinguished from one another, every key must be at least $\log_2 n$ bits. This is why, in radix sort, the number of digits is $d = \Theta(\log n)$, and the cost actually corresponds to $\Theta(n \log n)$ bit operations. The lower bound is not violated; a different unit of operation has been counted.

Extra space is required. None of the three is in-place; counting and bucket sort use $O(n + k)$ space.

Still, when the conditions hold, the gain is real: sorting millions of records by a fixed-width identifier field is noticeably faster with radix sort than with a comparison-based algorithm.

Summary

• The decision-tree argument shows that comparison-based sorting requires $\Omega(n \log n)$ comparisons in the worst case.
• The proof’s only assumption is that the algorithm only compares; the bound can be surpassed if the structure of the keys is used.
• Counting sort is $O(n + k)$ and stable on a small integer range; traversing in reverse order is the condition for stability.
• Bucket sort gives expected $O(n)$ under uniform distribution; the guarantee disappears if the distribution breaks down.
• Radix sort runs in $O(d(n + b))$ by using a stable sort at every digit.
• Claims of linearity depend on assumptions, and if key width depends on $n$, the lower bound reappears in a different unit.

Next Step

Seven algorithms and a set of distinct criteria have accumulated: worst case, stability, extra space, adaptivity, memory access pattern, and key structure. The next lesson gathers these into a single decision table and answers the question “which algorithm for which data”.