Non-Comparison Linear Time Sorts

Topics Covered:
56. Counting Sort (Frequency Hashing & Stable Reconstruction) • 57. Radix Sort (LSD vs MSD Positional Sorting) • 58. Bucket Sort (Uniform Distribution & Scatter-Gather)

Comparison-based sorting algorithms are fundamentally bound by the $\Omega (n\log n)$ decision tree lower bound. Non-comparison sorting algorithms—Counting Sort, Radix Sort, and Bucket Sort—bypass this mathematical barrier by exploiting algebraic and structural properties of the input keys rather than comparing relative magnitudes. By leveraging bounded integer ranges, positional digit decompositions, and continuous probability distributions, these algorithms achieve linear $\Theta (n)$ execution time. This chapter explores frequency histograms, prefix sum address calculation, multi-pass positional stability, bitwise radix extraction, and probabilistic scatter-gather architectures.

• Formulate how frequency histograms and cumulative prefix sums establish exact target indices in Counting Sort.
• Implement backward stable array reconstruction in Counting Sort and prove why backward traversal is mandatory for stability.
• Differentiate Least Significant Digit (LSD) from Most Significant Digit (MSD) Radix Sort, proving why LSD requires a stable sub-sorter.
• Analyze Radix Sort base selection trade-offs ($b=10$ vs $b=2^8=256$) for high-throughput 32-bit and 64-bit integer sorting.
• Formulate the scatter-sort-gather pipeline of Bucket Sort and prove its expected linear runtime under a continuous uniform distribution $U[0,1)$.

Counting Sort assumes that each of the $n$ input elements is an integer in the bounded range $[0,k]$. Rather than performing comparisons, it determines for each input element $x$ how many elements in the input are strictly smaller than $x$. With this count in hand, $x$ can be placed directly into its final position in the output array.

The algorithm operates in three distinct phases:

1. Histogram Construction: Compute a frequency histogram array $C[0\dots k]$ where $C[v]$ records the occurrences of value $v$ in input array $A$.
2. Cumulative Prefix Sums: Transform $C$ in place such that each cell $C[v]$ stores ${\sum }_{j=0}^{v}C[j]$. The value $C[v]$ indicates the total count of elements $\le v$, which defines the upper boundary of index positions where value $v$ belongs in the output.
3. Backward Stable Placement: Traverse the original array $A$ backwards from index $n-1$ down to $0$. For each element $A[i]$, place it at index $C[A[i]]-1$ in output buffer $B$, and decrement $C[A[i]]$.

Consider sorting the array $A=[4,2,2,8,3,3,1]$ of size $n=7$ with maximum key $k=8$:

Traversing $A=[4,2_a,2_b,8,3_a,3_b,1]$ from right to left ($i=6$ down to $0$):

Why Backward Traversal is Mandatory for Stability:
In step 5, duplicate $3_b$ (appearing later in $A$) was assigned output index 4. In step 4, duplicate $3_a$ (appearing earlier in $A$) was assigned output index 3. Because $3_a$ occupies a smaller index than $3_b$, their relative original order is strictly preserved. Traversing forward would place $3_a$ at 4 and $3_b$ at 3, inverting their order and destroying stability.

FUNCTION CountingSort(A: Array of Integer, n: Integer, k: Integer) -> Array of Integer:
    // Allocate count buffer of size k + 1 and output buffer of size n
    count <- Array of size (k + 1) initialized to 0
    output <- Array of size n

    // Phase 1: Build frequency histogram
    FOR i <- 0 TO n - 1 DO
        count[A[i]] <- count[A[i]] + 1
    END FOR

    // Phase 2: Compute cumulative prefix sums
    FOR j <- 1 TO k DO
        count[j] <- count[j] + count[j - 1]
    END FOR

    // Phase 3: Place elements backwards into output buffer
    FOR i <- n - 1 DOWNTO 0 DO
        val <- A[i]
        targetIdx <- count[val] - 1
        output[targetIdx] <- val
        count[val] <- count[val] - 1
    END FOR

    RETURN output

Complexity & Domain Constraints:

• Time Complexity: $\Theta (n+k)$ across all cases (best, average, worst). Building histogram takes $\Theta (n)$, prefix sums take $\Theta (k)$, and output placement takes $\Theta (n)$.
• Auxiliary Space: $\Theta (n+k)$ for the count array of size $k+1$ and output buffer of size $n$.
• Operational Boundary: Counting Sort is asymptotically optimal when $k=O(n)$, yielding $\Theta (n)$ time. If $k=\Omega (n^2)$ (e.g., sorting 10 integers where maximum value is $10^9$), the $\Theta (k)$ memory and runtime overhead makes it far worse than standard $O(n\log n)$ algorithms.

When integer keys span a wide numerical range $[0,k]$ where $k\gg n$, Counting Sort becomes impractical. Radix Sort overcomes this by decomposing each key into $d$ digits evaluated in a specific positional numerical base $b$:

• LSD (Least Significant Digit) Radix Sort: Sorts keys starting from the least significant digit (units position) toward the most significant digit (highest power of $b$).
• MSD (Most Significant Digit) Radix Sort: Sorts keys starting from the highest power of $b$ toward the units digit, recursively partitioning elements into sub-buckets (similar to a Trie or QuickSort).

The Fundamental LSD Theorem:
If an array is sorted by digit $j$ using an unconditionally stable sorting subroutine, then for any two keys whose digits at positions $\ge j$ are identical, their relative sorted order from previous digit passes $<j$ is strictly preserved. Therefore, sorting passes from least significant digit ($j=0$) to most significant digit ($j=d-1$) yields a globally sorted array.

Consider sorting eight 3-digit decimal numbers ($b=10,d=3$):
$A=[170,045,075,090,002,024,802,066]$

Notice that in Pass 2, $002$ and $802$ both have tens digit $0$. Because the digit sort is stable, $002$ remains before $802$ as established in Pass 1. In Pass 3, sorting by the hundreds digit places all numbers beginning with $0$ in front, perfectly ordered by their lower digits.

FUNCTION RadixSort(A: Array of Integer, n: Integer):
    maxVal <- FindMaximum(A, n)

    // Execute stable counting sort for each digit position: 1, 10, 100...
    exp <- 1
    WHILE FLOOR(maxVal / exp) > 0 DO
        CountingSortByDigit(A, n, exp)
        exp <- exp * 10
    END WHILE

FUNCTION CountingSortByDigit(A: Array of Integer, n: Integer, exp: Integer):
    output <- Array of size n
    count <- Array of size 10 initialized to 0

    // Count occurrences of current digit: (A[i] / exp) % 10
    FOR i <- 0 TO n - 1 DO
        digit <- FLOOR(A[i] / exp) MOD 10
        count[digit] <- count[digit] + 1
    END FOR

    // Prefix sums
    FOR j <- 1 TO 9 DO
        count[j] <- count[j] + count[j - 1]
    END FOR

    // Build output array backwards to guarantee stability
    FOR i <- n - 1 DOWNTO 0 DO
        digit <- FLOOR(A[i] / exp) MOD 10
        output[count[digit] - 1] <- A[i]
        count[digit] <- count[digit] - 1
    END FOR

    // Copy sorted output back to array A
    FOR i <- 0 TO n - 1 DO
        A[i] <- output[i]
    END FOR

The total runtime of LSD Radix Sort across $n$ keys with maximum value $k$ in base $b$ is:

Hardware-Optimized Base Selection:

When sorting 32-bit unsigned integers:

• Choosing decimal base $b=10$ requires $d=10$ passes, and integer division/modulo instructions (/ and %) which are computationally expensive on CPUs.
• Choosing base $b=2^8=256$ (1 byte per digit) allows digits to be extracted using instant bitwise shifts and bitmasks:
  $${\text{digit}}_j(x)=(x\gg (8\cdot j))\&\text{0xFF}$$
• Number of passes: $d=32/8=4$ passes.
• Frequency buffer size per pass: $b=256$ integers (fits effortlessly into L1 CPU cache).
• Total runtime: $4\times (n+256)=\mathbf{\Theta }(\mathbf{n})$.

On modern hardware, a 4-pass 8-bit Radix Sort routinely outperforms Quicksort by a factor of $2\times$ to $3\times$ when sorting millions of 32-bit integers.

Bucket Sort assumes that the input data is generated by a random process that distributes elements uniformly and independently over the continuous real interval $[0.0,1.0)$.

The algorithm proceeds through three phases:

1. Scatter: Divide $[0.0,1.0)$ into $n$ equal-width sub-intervals (buckets) of size $1/n$. For each element $A[i]$, map it to bucket index $b=\lfloor n\cdot A[i]\rfloor$ and insert it into a dynamic linked list or resizable array at buckets[b].
2. Sort: Sort each individual bucket independently using Insertion Sort.
3. Gather: Concatenate all sorted buckets in order from bucket $0$ to $n-1$ to form the final sorted array.

Consider sorting $n=10$ floating-point values:
$A=[0.78,0.17,0.39,0.26,0.72,0.94,0.21,0.12,0.23,0.68]$

Final concatenated array: $[0.12,0.17,0.21,0.23,0.26,0.39,0.68,0.72,0.78,0.94]$.

Let $n_i$ be a random variable denoting the number of elements placed into bucket $i$. Since each element has an equal probability $p=1/n$ of landing in any given bucket, $n_i$ follows a Binomial distribution $B(n,1/n)$.

The time required to sort bucket $i$ via Insertion Sort is $O(n_i^2)$. The total time across all buckets is:

For a Binomial random variable $n_i\sim B(n,p)$ with $p=1/n$:

• Mean: $E[n_i]=n\cdot p=n\cdot (1/n)=1$
• Variance: $\text{Var}(n_i)=np(1-p)=1-1/n$
• Second Moment:
  $$E[n_i^2]=\text{Var}(n_i)+(E[n_i]{)}^2=\left(1-\frac{1}{n}\right)+1^2=2-\frac{1}{n}$$

Substituting this into the total expected time summation:

Under the assumption of uniform distribution, the expected runtime of Bucket Sort is strictly linear $\Theta (n)$.

Failure Mode & Degeneracy:

If the input data is severely skewed (e.g., all $n$ elements share identical values and collapse into a single bucket), Insertion Sort must process all $n$ elements in that single bucket, degrading total runtime to $\Theta (n^2)$.

1. Circumventing Comparison Bounds: Non-comparison sorts bypass the $\Omega (n\log n)$ information-theoretic lower bound by using direct address indexing, digit extraction, or statistical partitioning.
2. Counting Sort Invariant: Cumulative prefix sums translate element frequencies into exact output array address bounds. Backward traversal from $n-1$ down to $0$ is strictly required to preserve stability.
3. Radix Sort Multi-Pass Stability: LSD Radix Sort requires an unconditionally stable sub-sorter so that decisions made on lower-significance digits remain intact during higher-significance passes.
4. Byte-Level Radix Efficiency: Configuring Radix Sort with base $b=256$ processes 32-bit integers in exactly 4 passes using efficient bitwise shifts and bitmasks without floating-point division.
5. Bucket Sort Distribution Dependence: Bucket Sort achieves average-case linear time only when keys follow a uniform probability distribution over continuous intervals; clustering or skewed distributions degrades performance to quadratic $O(n^2)$.

1. Seward, H. H. (1954). Information sorting in the application of electronic digital computers to business operations (First formal description of Counting Sort and Radix Sort). Master's thesis, Massachusetts Institute of Technology.
2. Knuth, D. E. (1998). The Art of Computer Programming, Volume 3: Sorting and Searching (2nd ed.), Section 5.2.5: Sorting by Distribution. Addison-Wesley.
3. Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2022). Introduction to Algorithms (4th ed.), Chapter 8: Sorting in Linear Time (Counting Sort, Radix Sort, Bucket Sort). MIT Press.
4. Sedgewick, R., & Wayne, K. (2011). Algorithms (4th ed.), Section 5.1: String Sorts (LSD and MSD Radix Sorting). Addison-Wesley.