Sorting in Linear Time

Chapter 1: Decision Tree Lower Bound

In Chapter 0 we saw the intuition: comparison sorts gather one bit per comparison, and they need enough bits to identify one of n! orderings. Now let us make this argument airtight.

The Model

A comparison sort is any sorting algorithm that determines the sorted order only by comparing pairs of input elements. Given elements a₁, a₂, ..., a_n, the algorithm may ask questions of the form "is a_i ≤ a_j?" and branch based on the answer. It may not look at the values of the elements directly — only at the results of comparisons.

We model any such algorithm as a decision tree:

The Theorem

Theorem 8.1 (CLRS): Any comparison sort algorithm requires Ω(n log n) comparisons in the worst case.

Proof. The decision tree must have at least n! leaves (one for each permutation of n elements — each permutation is a possible input ordering, and the algorithm must be able to produce each one as output). A binary tree of height h has at most 2^h leaves. Therefore:

Taking logarithms:

By Stirling's approximation, n! ≈ √(2πn) · (n/e)ⁿ, so:

This is why merge sort, heapsort, and the best quicksort variants all converge to O(n log n). They are optimal within the comparison model. To go faster, we must step outside the model entirely.

What the Lower Bound Does NOT Say

The lower bound says comparison sorts cannot beat Ω(n log n). It does not say:

1. That sorting itself is Ω(n log n). Only comparison-based sorting is. If you know the data is integers in [0, k], counting sort does it in O(n + k).

2. That all inputs require n log n comparisons. Many inputs are easier — insertion sort on nearly-sorted data is O(n). The lower bound is about the worst case.

3. That constant factors do not matter. Quicksort's O(n log n) average case has smaller constants than merge sort's O(n log n) worst case, which is why quicksort is often faster in practice despite a worse worst case.

Chapter 2: Counting Sort

Merge sort asks "which of these two elements is smaller?" over and over. But what if you already know where each element belongs — because you know its value, and you know how many elements are smaller? That is counting sort.

The Algorithm

Suppose you have n integers, each in the range [0, k]. Counting sort works in three passes:

Worked Example

Input A = [2, 5, 3, 0, 2, 3, 0, 3], range k = 5.

Pass 1 (count): C = [2, 0, 2, 3, 0, 1]. Value 0 appears twice, value 2 appears twice, value 3 appears three times, value 5 appears once.

Pass 2 (prefix sum): C = [2, 2, 4, 7, 7, 8]. This means: elements ≤ 0 occupy positions 0-1, elements ≤ 2 occupy positions 0-3, elements ≤ 3 occupy positions 0-6, elements ≤ 5 occupy positions 0-7.

Pass 3 (place, right to left):

Result: [0, 0, 2, 2, 3, 3, 3, 5]. Sorted. No comparisons made.

Complexity

Space: O(n + k) — the output array B[0..n-1] plus the count array C[0..k].

When is this useful? When k (the range of values) is not much larger than n. Sorting a million exam scores in [0, 100]? k = 100, n = 1,000,000. O(n + k) = O(n). Brilliant. Sorting a million 64-bit integers? k = 2⁶⁴. The count array alone would not fit in any computer's memory. Terrible. For large ranges, we need radix sort.

Code

python
def counting_sort(A, k):
    """Sort array A of integers in [0, k]. Returns new sorted array."""
    n = len(A)
    C = [0] * (k + 1)   # count array
    B = [0] * n           # output array

    # Pass 1: count occurrences
    for val in A:
        C[val] += 1

    # Pass 2: prefix sums
    for i in range(1, k + 1):
        C[i] += C[i - 1]

    # Pass 3: place elements (right-to-left for stability)
    for i in range(n - 1, -1, -1):
        val = A[i]
        C[val] -= 1
        B[C[val]] = val

    return B

Chapter 3: Radix Sort

Counting sort is brilliant when the range k is small. But what if your integers are large — say, 9-digit numbers? k = 999,999,999 and a count array that big is absurd. Radix sort solves this by sorting one digit at a time, using counting sort on each digit position.

The Key Insight: Sort Least Significant Digit First

Your first instinct might be to sort by the most significant digit first, like sorting words in a dictionary (alphabetical from left). But that creates subproblems: after grouping by the first digit, you must recursively sort within each group. That is MSD (Most Significant Digit) radix sort — it works, but it is recursive and complex.

LSD (Least Significant Digit) radix sort is simpler and more elegant. You sort by the last digit first, then the second-to-last, and so on. It sounds backwards, but it works perfectly — as long as each digit-sort is stable.

Worked Example

Sort: [329, 457, 657, 839, 436, 720, 355]

Pass 1 — sort by ones digit (d=1):

After pass 1: [720, 355, 436, 457, 657, 329, 839]. Note: 457 before 657 (stable), 329 before 839 (stable).

Pass 2 — sort by tens digit (d=2):

After pass 2: [720, 329, 436, 839, 355, 457, 657]. Stability preserved: 720 before 329 (both tens digit 2, and 720 was before 329 after pass 1).

Pass 3 — sort by hundreds digit (d=3):

After pass 3: [329, 355, 436, 457, 657, 720, 839]. Fully sorted.

Complexity

In practice, radix sort with base 256 (8-bit digits, d = 4 for 32-bit integers) is extremely fast. Four passes of counting sort, each operating on just 256 buckets. Cache-friendly, branch-free, and predictable.

Code

python
def radix_sort(A, base=10):
    """LSD radix sort for non-negative integers."""
    if not A:
        return A
    max_val = max(A)
    exp = 1  # current digit position
    while max_val // exp > 0:
        A = _counting_sort_by_digit(A, exp, base)
        exp *= base
    return A

def _counting_sort_by_digit(A, exp, base):
    """Stable counting sort on the digit at position exp."""
    n = len(A)
    B = [0] * n
    C = [0] * base

    # Count digit occurrences
    for val in A:
        digit = (val // exp) % base
        C[digit] += 1

    # Prefix sums
    for i in range(1, base):
        C[i] += C[i - 1]

    # Place (right-to-left for stability)
    for i in range(n - 1, -1, -1):
        digit = (A[i] // exp) % base
        C[digit] -= 1
        B[C[digit]] = A[i]

    return B

Chapter 4: Bucket Sort

Counting sort assumes integers in a known range. Radix sort assumes integers (or strings) you can decompose digit-by-digit. What if your data is floating-point numbers uniformly distributed in [0, 1)? Neither counting sort nor radix sort applies cleanly. Enter bucket sort.

The Algorithm

The idea is beautifully simple: if n numbers are uniformly distributed in [0, 1), divide the interval into n equal-sized buckets [0, 1/n), [1/n, 2/n), ..., [(n-1)/n, 1). On average, each bucket gets about one element. Sort each bucket (with insertion sort — efficient for tiny lists), then concatenate.

Worked Example

Input A = [0.78, 0.17, 0.39, 0.26, 0.72, 0.94, 0.21, 0.12, 0.23, 0.68], n = 10.

Concatenated: [0.12, 0.17, 0.21, 0.23, 0.26, 0.39, 0.68, 0.72, 0.78, 0.94].

Expected Time Analysis

Expected time: O(n) when input is uniformly distributed. Worst case: O(n²) when all elements land in the same bucket.

Code

python
def bucket_sort(A):
    """Sort floats in [0, 1) using bucket sort."""
    n = len(A)
    buckets = [[] for _ in range(n)]

    # Distribute into buckets
    for x in A:
        idx = int(n * x)
        if idx == n:  # edge case: x = 1.0
            idx = n - 1
        buckets[idx].append(x)

    # Sort each bucket (insertion sort)
    for b in buckets:
        _insertion_sort(b)

    # Concatenate
    result = []
    for b in buckets:
        result.extend(b)
    return result

def _insertion_sort(A):
    """In-place insertion sort."""
    for i in range(1, len(A)):
        key = A[i]
        j = i - 1
        while j >= 0 and A[j] > key:
            A[j + 1] = A[j]
            j -= 1
        A[j + 1] = key

Chapter 5: The Sorting Arena

Time for the payoff. Below is a head-to-head comparison of every sorting algorithm we have studied: three comparison-based sorts (merge sort, quicksort, heapsort) and three linear-time sorts (counting sort, radix sort, bucket sort). You control the data — its size, its range, and its distribution. Watch the operation counts diverge as you find each algorithm's sweet spot and its weakness.

What to Try

The lesson: there is no universally best sorting algorithm. The right choice depends on your data. Knowing these five factors — range, distribution, data type, stability needs, and memory budget — is what separates a junior programmer from an engineer.

Chapter 6: When to Use Which

A sort algorithm is a tool. Like any tool, the question is not "which is best?" but "which is best for this job?" Here is the decision framework.

Decision Tree

The Complete Comparison

*Bucket sort is stable if the sub-sort is stable (insertion sort is stable).

Real-World Usage

Chapter 7: Stability

Two students both scored 85 on the midterm. In the original roster, Alice is listed before Bob. After sorting by score, a stable sort keeps Alice before Bob. An unstable sort might swap them.

This sounds like a minor detail. It is not. Stability is the reason radix sort works. It is the reason database sorts compose. It is a property that interviewers ask about because it reveals whether you understand sorting at a deep level.

Formal Definition

A sorting algorithm is stable if, whenever two elements have equal keys, they appear in the output in the same relative order as in the input. Formally: if A[i] = A[j] and i < j, then in the sorted output, A[i] appears before A[j].

Why Stability Matters

1. Multi-key sorting. You want to sort students by grade, then by name within each grade. If you sort by name first, then sort by grade with a stable sort, students with the same grade remain in alphabetical order. Two stable sorts compose into a multi-key sort. This is exactly how radix sort works: sort by LSD, then next digit, etc.

2. Preserving meaningful order. Database rows often have a "natural" order (insertion time, row ID). A stable sort preserves this order among ties, which users expect.

3. Correctness of radix sort. If the digit-level sort is unstable, radix sort breaks. The LSD-first strategy relies on stability to preserve the order established by previous digit passes.

Stability Classification

Making an Unstable Sort Stable

Any sort can be made stable by appending the original index as a tiebreaker. If a[i] = a[j] and i < j, compare as (a[i], i) < (a[j], j). This always breaks ties in favor of the earlier element. The cost: O(n) extra space for the index array, and slightly larger comparisons.

python
def stable_sort(A):
    """Make any sort stable by using (value, index) pairs."""
    decorated = [(val, i) for i, val in enumerate(A)]
    decorated.sort()  # Python's sort compares tuples lexicographically
    return [val for val, _ in decorated]

Chapter 8: Interview Arsenal

This is your reference chapter. Cheat sheets, coding drills, and the patterns that interviewers love to test.

The Master Cheat Sheet

Coding Drill 1: Counting Sort

Implement counting sort from memory. This is a common interview question because it tests whether you understand prefix sums and stability.

python
# Drill: implement from scratch in 2 minutes
def counting_sort(A, k):
    C = [0] * (k + 1)
    B = [0] * len(A)

    for x in A:             # count
        C[x] += 1

    for i in range(1, k+1): # prefix sum
        C[i] += C[i-1]

    for i in range(len(A)-1, -1, -1):  # place (R-to-L)
        C[A[i]] -= 1
        B[C[A[i]]] = A[i]

    return B

Coding Drill 2: Sort by Frequency

Given an array, sort elements by frequency (most frequent first). If two elements have the same frequency, maintain their order of first appearance. This combines counting and stability.

python
from collections import Counter

def sort_by_frequency(A):
    """Sort by frequency (descending). Stable for ties."""
    freq = Counter(A)
    # Decorate-sort-undecorate
    # Key: (-frequency, first_occurrence_index)
    first_seen = {}
    for i, x in enumerate(A):
        if x not in first_seen:
            first_seen[x] = i

    return sorted(A, key=lambda x: (-freq[x], first_seen[x]))

# Example: [1,1,2,2,2,3] -> [2,2,2,1,1,3]

Coding Drill 3: Top K Frequent Elements

Given n elements, find the k most frequent. Bucket sort approach: O(n) time.

python
from collections import Counter

def top_k_frequent(A, k):
    """O(n) using bucket sort by frequency."""
    freq = Counter(A)
    n = len(A)

    # Buckets: index = frequency, value = list of elements
    buckets = [[] for _ in range(n + 1)]
    for val, count in freq.items():
        buckets[count].append(val)

    # Collect from highest frequency down
    result = []
    for i in range(n, 0, -1):
        for val in buckets[i]:
            result.append(val)
            if len(result) == k:
                return result
    return result

# Example: top_k_frequent([1,1,1,2,2,3], 2) -> [1, 2]

Coding Drill 4: Radix Sort for Strings

Radix sort is not just for integers. You can sort fixed-length strings by applying counting sort to each character position, from right to left (LSD).

python
def radix_sort_strings(A, strlen):
    """LSD radix sort for fixed-length ASCII strings."""
    R = 256  # alphabet size (ASCII)
    for d in range(strlen - 1, -1, -1):
        # Counting sort by character at position d
        C = [0] * R
        B = [""] * len(A)

        for s in A:
            C[ord(s[d])] += 1
        for i in range(1, R):
            C[i] += C[i-1]
        for i in range(len(A)-1, -1, -1):
            ch = ord(A[i][d])
            C[ch] -= 1
            B[C[ch]] = A[i]
        A = B

    return A

Common Interview Questions

Chapter 9: Connections

Linear-time sorting does not exist in a vacuum. Every algorithm in this chapter builds on ideas from earlier chapters and opens doors to later ones.

Where It Connects

The Hierarchy of Sorting Knowledge

This lesson brought you through levels 1-3. Level 4 comes with experience — writing production code that sorts billions of records, profiling cache misses in radix sort, and understanding why NVIDIA's CUB library uses a 4-bit radix.

"The purpose of computing is insight, not numbers." — Richard Hamming