Counting Sort and Radix Sort

For decades, the theoretical limit for general-purpose sorting was thought to be $O(n\log n)$, the best that comparison-based algorithms like Merge Sort or QuickSort can achieve. However, by exploiting the structure of the data itself—specifically, by sorting integers without direct comparisons—we can break this barrier and achieve linear time complexity. Counting Sort and Radix Sort are two powerful, non-comparison-based algorithms that do exactly this, providing exceptional performance in specialized but common scenarios like sorting database keys, pixel values, or phone numbers.

The Foundation: How Counting Sort Works

Counting Sort operates on a simple but powerful principle: if you know the exact range of integer values in your input array, you can sort by counting occurrences and calculating final positions directly. The algorithm does not compare elements against each other. Instead, it tallies frequencies to place items in their correct sorted order in a single pass.

The process has three main phases. First, you create a count array of size $k$, where $k$ is the range of possible input values (from minimum to maximum). You iterate through the input array, and for each element arr[i], you increment count[arr[i]]. This gives you a frequency distribution. Second, you transform this count array into a prefix sum array. You modify count so that each element count[i] contains the number of elements less than or equal to i. This value effectively becomes the last index (plus one) where the element i should be placed in the output. Finally, you build the sorted output array by iterating through the original input from right to left (this is crucial for stability). For each element, you use the prefix sum in count to find its correct position in the output, place it there, and decrement the count value.

Consider sorting the array [4, 2, 2, 8, 3, 3, 1] where the range is 1 to 8 ($k=8$). The count array becomes [0,1,2,2,1,0,0,0,1] (index 0 is unused, value 1 appears once, value 2 appears twice, etc.). The prefix sum is [0,1,3,5,6,6,6,6,7]. Placing the last input element (1) using the prefix sum index (1) gives us the start of the sorted array. The algorithm's time complexity is $O(n+k)$, where $n$ is the number of elements and $k$ is the range of input values. Its space complexity is $O(n+k)$ for the output and count arrays.

Extending the Concept: Radix Sort

Radix Sort generalizes the idea of Counting Sort to handle numbers with multiple digits or strings with multiple characters. Instead of sorting based on the entire value, it sorts digit by digit or character by character, from the least significant digit (LSD) to the most significant. Each individual sort must be stable—meaning items with the same key in the current pass retain their relative order from the previous pass. This stability ensures that the work done in sorting lower-order digits is not undone when sorting higher-order digits.

The algorithm works by taking each number and processing its individual digits. For example, to sort [170, 45, 75, 90, 802, 24, 2, 66], you would first sort solely based on the units place (0,5,5,0,2,4,2,6). A stable sort would yield [170, 90, 802, 2, 24, 45, 75, 66]. Next, you sort this result based on the tens place, then the hundreds place. After the final pass, the entire list is ordered. Since each digit is a finite integer (e.g., 0-9), Counting Sort is the ideal, stable subroutine for each pass.

The time complexity of Radix Sort is $O(d\cdot (n+k))$, where $d$ is the number of digits, $n$ is the number of elements, and $k$ is the radix or base (e.g., $k=10$ for decimal). Crucially, if $d$ is constant and $k=O(n)$, the overall time becomes linear: $O(n)$. This makes it exceptionally fast for sorting large sets of fixed-width data, like 32-bit integers, where $d$ is at most 10 for base-10 or 32 for base-2, and both are constants independent of $n$.

Stability: The Non-Negotiable Requirement

For Radix Sort to function correctly, the digit-by-digit sorting subroutine must be stable. Stability ensures that when two elements have the same key in the current sorting pass, their existing order from the previous pass is preserved. This is what allows the algorithm to build a correct global order incrementally. For instance, after sorting by the units digit, the numbers 90 and 170 (both with a '0' in the units place) will appear in some order. When we then sort by the tens digit, both have a '9'. A stable sort will keep 90 before 170 if that was their relative order after the units pass, correctly placing 90 < 170 in the final sorted list.

Counting Sort is naturally stable when implemented correctly—specifically, when the output is built by iterating through the input array from the last element to the first. This reverse traversal, combined with decrementing prefix sums, ensures that identical values are placed in the output in the same order they appeared in the input. This property is why Counting Sort and Radix Sort are almost always discussed together; Counting Sort provides the perfect stable, linear-time building block for Radix Sort's multi-pass approach.

When Linear-Time Sorts Outperform Comparison Sorts

The primary advantage of Counting Sort and Radix Sort is their potential for $O(n)$ linear time complexity, which beats the $O(n\log n)$ lower bound of comparison-based sorts. However, this advantage is conditional and comes with specific constraints.

These algorithms excel when:

• The data consists of integers or strings. They rely on having a discrete, indexable key (like a digit or character).
• The range of key values ($k$) is not excessively large compared to $n$. For Counting Sort, if $k$ is $O(n)$ or $O(n\log n)$, the $O(n+k)$ performance is excellent. If $k$ is huge (e.g., sorting a few numbers in a range of billions), the algorithm becomes impractical due to memory usage.
• For Radix Sort, the number of digits ($d$) is relatively small. Sorting a list of ten thousand 10-digit numbers is fast. Sorting ten numbers with a thousand digits each is not.

In contrast, comparison-based algorithms like QuickSort or HeapSort are more general-purpose. They work on any data type for which a comparison function can be defined (e.g., custom objects) and do not require auxiliary knowledge about the data's range. They are often more cache-efficient and have lower constant factors for in-place sorting. Therefore, the choice is situational: use Counting/Radix Sort for large volumes of bounded integer data (like database indices or pixel values); use comparison sorts for general, heterogeneous, or complex data.

Common Pitfalls

1. Ignoring the Range Constraint: Attempting to use Counting Sort on data with an enormous range (e.g., 32-bit integers where $k$ is over 4 billion) will allocate a proportionally huge count array, wasting memory and often making the algorithm slower than a simple $O(n\log n)$ sort. Always assess if $k$ is reasonable relative to $n$.
2. Breaking Stability in Implementation: A subtle bug in Counting Sort—such as building the output array by iterating from the first element instead of the last—will break its stability. This will cause Radix Sort, which depends on that stability, to produce incorrect results. Always double-check the final placement loop.
3. Misapplying to Non-Integer Data: These algorithms work directly on integer keys. Trying to use them directly on arbitrary objects (like employee records) requires careful extraction of an integer key (like an ID). Applying them to floating-point numbers without special consideration is problematic due to precision and representation issues.
4. Overlooking Space Complexity: Both algorithms are not in-place; they require significant additional memory ($O(n+k)$). In memory-constrained environments, an in-place comparison sort might be preferable even if it is asymptotically slower.

Summary

• Counting Sort is a non-comparison, integer sorting algorithm that tallies frequencies into a count array and uses prefix sums to place elements directly, achieving $O(n+k)$ time complexity where $k$ is the input range.
• Radix Sort sorts numbers digit-by-digit (LSD to MSD) using a stable subroutine like Counting Sort for each pass, resulting in a time complexity of $O(d\cdot (n+k))$.
• Stability is critical for Radix Sort, and a correctly implemented Counting Sort provides this property by processing the input in reverse order during the final placement step.
• These linear-time algorithms outperform comparison-based sorts ($O(n\log n)$) when sorting large quantities of integers with bounded ranges and digit counts, but are less general-purpose and require more auxiliary memory.
• Successful implementation requires careful attention to data constraints (range $k$, digit count $d$) and adherence to the stable sorting procedure to avoid incorrect results.