How Do Counting Sort and Radix Sort Beat O(n log n)?

Classical comparison-based sorting algorithms cannot run faster than linearithmic time in the worst case because each comparison only yields a single bit of information about the relative order of two elements. Counting Sort and Radix Sort bypass this fundamental lower bound by avoiding pairwise comparisons altogether and instead using the numeric values of integer keys as direct array indices or digit-by-digit buckets. By exploiting the bounded range and fixed-width representation of integer keys in classical computing, these non-comparison algorithms achieve linear time complexity when the key range or digit count is small relative to the input size.

The Comparison-Based Lower Bound

Any sorting algorithm that relies solely on pairwise comparisons (such as Merge Sort, Quicksort, or Heapsort) can be modeled as a binary decision tree. Each internal node represents a comparison \(a_i \le a_j\), and each leaf represents one of the \(n!\) possible permutations of the \(n\) input elements.

For the algorithm to be correct, the decision tree must have at least \(n!\) leaves. A binary tree of height \(h\) has at most \(2^h\) leaves, which means:

\[2^h \ge n! \implies h \ge \log_2(n!)\]

Using Stirling's approximation, \(\log_2(n!) = \Omega(n \log n)\). Because the worst-case number of comparisons equals the height \(h\) of the tree, no comparison-based sorting algorithm can beat \(\Omega(n \log n)\) in the worst case.

How Counting Sort Uses Direct Addressing

Counting Sort sidesteps the decision-tree model by assuming that all \(n\) input keys are integers within a known, bounded range \([0, k - 1]\). Instead of comparing elements to one another, it uses the integer value of each key as a direct index into an auxiliary frequency array of size \(k\).

The algorithm proceeds in three main steps:

  1. Count the occurrences of each key \(x\) by incrementing \(\text{count}[x]\) in \(O(n)\) time.
  2. Compute prefix sums over the \(\text{count}\) array in \(O(k)\) time so that \(\text{count}[x]\) stores the final sorted position of key \(x\).
  3. Iterate backward through the input array and place each element into its computed output position, preserving stability, in \(O(n)\) time.

The total time complexity is \(O(n + k)\), and the space complexity is \(O(n + k)\). When \(k = O(n)\), Counting Sort runs in \(O(n)\) time. Rather than extracting \(1\) bit of information per operation, direct array indexing effectively performs a \(k\)-way branch in \(O(1)\) time using the random-access memory (RAM) model.

How Radix Sort Scales to Larger Integers

Counting Sort becomes impractical when \(k\) is much larger than \(n\) (for example, sorting \(1{,}000\) 64-bit integers). Radix Sort overcomes this by decomposing each integer key into \(d\) digits in base \(b\), where \(k \le b^d\).

It sorts the keys digit by digit, typically from the least significant digit (LSD) to the most significant digit (MSD), using a stable sorting algorithm such as Counting Sort as a subroutine for each pass. Because each digit is in the range \([0, b - 1]\), each pass takes \(O(n + b)\) time. Across \(d\) passes, the total time complexity is:

\[O(d(n + b))\]

If the keys are bounded by \(U\), then \(d = \lceil \log_b U \rceil\). By choosing the base \(b = \Theta(n)\), the number of passes becomes \(d = O(\log_n U)\). When \(U = n^{O(1)}\) (polynomial in \(n\)), \(d\) is a constant, and Radix Sort achieves \(O(n)\) time complexity.

Classical Computing Assumptions and Trade-offs

Counting Sort and Radix Sort do not violate information theory; they simply operate outside the comparison model by leveraging hardware properties of classical computers:

  • Constant-Time Random Access: The classical RAM model allows indexing into an array of size \(k\) in \(O(1)\) time, which is not available in a pure comparison-only model.
  • Fixed-Width Integer Representation: Classical CPUs store integers in fixed-width binary words (such as 32-bit or 64-bit registers), allowing bit-shifting and masking to extract digits in \(O(1)\) time.
  • Space-Time Trade-off: Both algorithms require \(O(n + k)\) or \(O(n + b)\) auxiliary memory, trading extra space for linear-time execution.

When keys are arbitrary objects without a compact integer representation, or when \(k\) grows exponentially with \(n\), comparison-based \(\Omega(n \log n)\) algorithms remain the standard choice.