Radix Sort and Counting Sort Explained

Radix sort and counting sort are sorting algorithms that never compare two elements against each other — instead they exploit the structure of the values themselves, which lets them beat the comparison-based lower bound and sort in linear time under the right conditions. Every comparison sort, including quicksort and mergesort, is bounded below by O(n log n) because a comparison-based algorithm has to distinguish between n! possible orderings. Counting and radix sort sidestep that bound entirely by not comparing at all.

Counting sort: count, then place

Counting sort works when you’re sorting integers (or anything mappable to a small range of integers) and you know the range in advance. The idea is simple:

1. Count how many times each value appears, using an auxiliary array indexed by value.
2. Convert those counts into a running total (a prefix sum), so each count now tells you the position where that value’s block ends in the sorted output.
3. Walk the input again, placing each element at its position and decrementing the running count.

For an input array of n elements with values in the range [0, k), this runs in O(n + k) time using O(n + k) extra space. If k is small relative to n — say, sorting exam scores from 0 to 100 — this is dramatically faster than a comparison sort. If k is huge (sorting arbitrary 64-bit integers), the counting array itself becomes impractically large, and this is exactly the gap radix sort fills.

Counting sort is also stable: elements with equal keys keep their relative order, which matters when you’re sorting records by one field but want to preserve the existing order for ties. That stability property is also what makes it usable as a building block for radix sort.

Radix sort: sort digit by digit

Radix sort sorts multi-digit numbers (or fixed-length strings) by processing one digit position at a time, using counting sort as the underlying single-digit sort. The critical trick is the order: least significant digit (LSD) radix sort processes the ones digit first, then the tens digit, then the hundreds digit, and so on.

Why start from the least significant digit rather than the most significant? Because counting sort is stable. Sorting by the ones digit first, then re-sorting the whole (already ones-sorted) array by the tens digit, preserves the ones-place ordering among elements that tie on the tens digit — and by the time you’ve processed the most significant digit, every prior digit’s relative order has been correctly folded in.

For d-digit numbers in base b, radix sort runs in O(d · (n + b)) — a single counting-sort pass per digit. When d is a constant (say, sorting 32-bit integers as eight base-16 digits), that’s O(n) overall: genuinely linear, not just linear in appearance.

A worked example

Sorting [170, 45, 75, 90, 802, 24, 2, 66] with LSD radix sort in base 10:

• Pass 1 (ones digit): 170, 90, 802, 2, 24, 45, 75, 66
• Pass 2 (tens digit): 802, 2, 24, 45, 66, 170, 75, 90
• Pass 3 (hundreds digit): 2, 24, 45, 66, 75, 90, 170, 802

Three passes, each a stable counting sort on one digit, and the array is fully sorted.

Where these algorithms fit

	Counting sort	Radix sort	Quicksort / mergesort
Time complexity	O(n + k)	O(d(n + b))	O(n log n)
Comparison-based	No	No	Yes
Works on	Small-range integers	Fixed-width integers or strings	Anything with a total order
Stable	Yes	Yes (if base sort is stable)	Depends on implementation
Extra space	O(n + k)	O(n + b)	O(log n) to O(n)

The catch is generality. Comparison sorts work on anything you can define a < operator for — floats, strings, custom objects with arbitrary comparison logic. Counting and radix sort need a bounded, discretizable key space, which is why they’re most at home sorting integers, fixed-length strings, or fixed-precision numeric keys rather than arbitrary comparable objects.

When to actually reach for them

In practice, general-purpose sort routines in most languages use a comparison sort (often a hybrid like Timsort or introsort) because it’s correct for arbitrary types with no extra assumptions. Radix and counting sort earn their keep in more specialized situations:

• Sorting large volumes of fixed-width integer keys — record IDs, timestamps truncated to a fixed range, IP addresses — where the range is known and not enormous.
• Bucket-based preprocessing steps in data pipelines, where a coarse radix pass narrows the range before a finer sort.
• Suffix array construction and other string algorithms that already need character-by-character processing, where radix sort’s digit-wise structure is a natural fit.
• Situations where stability is a hard requirement and the key space happens to be small — counting sort gives you both for free.

They’re a poor fit when keys are high-precision floats, arbitrary-length strings with no fixed bound, or objects whose ordering is defined by custom comparison logic rather than a discrete key — in those cases the constant factors and space overhead of a bounded-range algorithm work against you, and a well-implemented comparison sort wins.

The takeaway

Comparison sorts are bounded by O(n log n) because they only learn about the data through pairwise comparisons. Counting sort and radix sort break past that bound by using the structure of integer keys directly — counting occurrences and placing elements by position instead of comparing them. Counting sort alone handles small, bounded ranges in O(n + k); radix sort extends that to wider ranges by sorting one digit at a time with a stable counting sort underneath. The tradeoff is generality: they need a bounded, discrete key space, which is exactly what general-purpose sort routines can’t assume.