Linear-Time Sorting: Counting, Radix and Bucket Sort

• Elementary Sorting: stability (essential here) and insertion sort (used inside bucket sort).
• Arrays with 1-based indexing; counting arrays are indexed from 0.

COUNTING-SORT(A, B, n, k)
    for v <- 0 to k
        C[v] <- 0
    for j <- 1 to n                    // count each key
        C[A[j]] <- C[A[j]] + 1
    for v <- 1 to k                    // C[v] = number of keys <= v
        C[v] <- C[v] + C[v - 1]
    for j <- n downto 1                // place, right to left
        B[C[A[j]]] <- A[j]
        C[A[j]] <- C[A[j]] - 1

Worked example

Analysis

• Time $\Theta(n + k)$: two loops over $n$, two over $k$. Linear when $k = O(n)$; poor when $k \gg n$ (for example sorting 10 numbers below $10^9$).
• Space $\Theta(n + k)$ auxiliary (arrays $B$ and $C$): not in place.
• Best, average and worst cases are the same: it never compares keys.
• Stable; works for records with integer keys, not only for bare integers.
• Negative keys or keys in $a..b$: shift by $-a$ and use $k = b - a$.

RADIX-SORT(A, d)
    for i <- 1 to d                     // digit 1 is the least significant
        use a stable sort to sort A on digit i

Worked example

Analysis

• With counting sort as the stable per-digit sort and digits in $0..k-1$: each pass is $\Theta(n + k)$, so the total is $\Theta(d(n + k))$. Linear when $d$ is constant and $k = O(n)$.
• Choosing the digit size. For integer $1\le r\le b$ and $n$ keys of $b$ bits, split each key into $\lceil b/r \rceil$ digits of $r$ bits; then $k = 2^r$ and the time is $\Theta(\lceil b/r\rceil(n + 2^r))$. Taking $r \approx \lg n$ (for $b \ge \lg n$) gives $\Theta(bn / \lg n)$. Example: $n = 2^{16}$ keys of $b = 32$ bits with $r = 16$ need 2 passes with $k = 65536$.
• Space $\Theta(n + k)$ with counting sort; not in place.
• Stable (if every pass is stable).
• Most significant digit first works only with recursion into each bucket (MSD radix sort); running plain passes from the most significant digit gives a wrong result. On the worked example, stable passes on hundreds, then tens, then units end with 720 355 436 457 657 329 839: the last pass wins, so the list is ordered primarily by the units digit.
• For $n\ge2$ and a fixed integer $c\ge1$, integers $0\le x<n^c$ can be sorted in $\Theta(n)$ time: write them in base $n$, using $c$ digits in $0..n-1$.

BUCKET-SORT(A, n)
    create empty lists B[0..n-1]
    for i <- 1 to n
        insert A[i] into list B[floor(n * A[i])]
    for i <- 0 to n - 1
        sort list B[i] with insertion sort
    concatenate B[0], B[1], ..., B[n-1] in order

Analysis

• Distribution and concatenation: $\Theta(n)$.
• If $n_i$ is the size of bucket $i$, insertion sort costs $O(n_i^2)$. Under the uniform assumption, $E[n_i^2] = 2 - 1/n$, so the expected total is $\Theta(n) + n \cdot O(2 - 1/n) = \Theta(n)$.
• Worst case $\Theta(n^2)$: if all keys fall into one bucket, insertion sort runs on all $n$. Using merge sort inside buckets lowers the worst case to $O(n \lg n)$.
• Space $\Theta(n)$ for the buckets. Stable if insertion into buckets appends and the bucket sort is stable.
• The linear bound holds more generally whenever the sum of the squares of the bucket sizes is linear in expectation; with a non-uniform but known distribution, choose bucket boundaries at its quantiles.

• These algorithms do not contradict the $\Omega(n \lg n)$ lower bound: it applies only to algorithms that learn about keys by comparisons.
• Counting sort is the standard stable subroutine for radix sort. Replacing it by an unstable sort (for example, quicksort on each digit) breaks radix sort.
• "Linear" depends on the parameters: counting sort with $k = n^2$ is $\Theta(n^2)$; radix sort with $d = \Theta(\lg n)$ digits and $k=O(n)$ is $\Theta(n \lg n)$; in general its cost is $\Theta(d(n+k))$.
• Counting sort can also count, for each value, how many keys are $\le$ it: range-count queries in $O(1)$ after $\Theta(n + k)$ preprocessing.

• Counting sort traces. the count array $C$ after counting and after prefix sums, and the position each element lands in. Remember the right-to-left final loop.
• Radix sort traces. the list after a given pass; each pass must keep ties in their previous order.
• Complexity with parameters. express time in $n$, $k$, $d$ or $b$ and $r$; decide whether it is linear.
• Traps. radix sort needs a stable digit sort and must go from the least significant digit (the last pass decides the primary order); counting sort's final loop must run right to left when $C$ holds last positions; bucket sort's linear time is an expectation under the uniform assumption.

• Elementary Sorting: prerequisite. Stability and insertion sort.
• Comparison of Sorting Algorithms: related. The comparison lower bound these algorithms avoid.
• Random Variables: related. Expectation used in the bucket sort analysis.