Radix Sort sorts numbers without ever comparing two of them directly. It processes one digit position at a time and uses a stable sorting algorithm like Counting Sort to reorder elements at each position. Repeating this across all digit positions produces a fully sorted array.

It runs in O(d * (n + k)) time, where d is the number of digits and k is the radix (10 for decimal). This makes it efficient for large sets of integers or fixed-length strings.

This chapter covers how Radix Sort works, how it builds on Counting Sort, and when it outperforms comparison-based sorting algorithms.

Radix sort is a non-comparison sorting algorithm that processes elements one digit (or character) at a time. Instead of asking "is A greater than B?", it groups elements by the value of a specific digit position, then repeats for the next position until all positions have been processed.

The word "radix" means "base", as in the base of a number system. For decimal numbers, the radix is 10 (digits 0-9). For binary strings, the radix is 2. For lowercase English letters, the radix is 26.

Two Variants

There are two ways to process the digit positions:

Each pass uses a stable sort as a subroutine. Stability means that elements with the same digit value retain their relative order from the previous pass. Without stability, sorting by the tens digit would destroy the ordering produced by the ones-digit pass. Counting sort is commonly used as the subroutine because it is stable, runs in O(n + k) time, and works well for small ranges of values (like digits 0-9).

LSD vs MSD: A Quick Comparison

The LSD radix sort algorithm follows these steps:

Extracting a Digit

The digit at a given position is isolated with this formula:

Where position is 1 for the ones digit, 10 for the tens digit, 100 for the hundreds digit, and so on.

For example, to extract the tens digit of 753:

Why Does LSD Work?

Sorting by the least significant digit first produces a correct result because of stability. After sorting by the ones digit, all numbers with the same ones digit are grouped together. Sorting by the tens digit next groups numbers with the same tens digit, and within each group the relative order from the ones-digit pass is preserved. By the time the most significant digit is processed, each pass has refined the ordering, and stability ensures that earlier passes are never undone.

This is the same effect as sorting a spreadsheet by column C, then by column B, then by column A: the final result is sorted primarily by A, then by B within ties, then by C within further ties.

Counting Sort as Subroutine

Radix sort needs a version of counting sort that sorts based on a specific digit position rather than the full value. The exp parameter indicates which digit position is being sorted (1 for ones, 10 for tens, 100 for hundreds).

Where:

When Is Radix Sort Faster Than O(n log n)?

Radix sort beats comparison-based sorts when d (n + k) < n log(n). Since k is typically small (10 for decimal), this simplifies to roughly d < log(n).

For 1 million 32-bit integers, log2(1,000,000) is about 20, and the maximum number of decimal digits is 10. So d = 10 < 20 = log(n), and radix sort wins. For sorting 10 numbers with 100 digits each, comparison sorts are faster.

Radix sort is well-suited to large datasets where the number of digits is small.

Stability

LSD radix sort is stable, and stability is required for the algorithm to produce a correct result. Each pass sorts by one digit while preserving the order established by previous passes. The earlier passes sorted by less significant digits, so within each group of equal current-digit values, the elements are already in the correct relative order; stability keeps them that way.

This is why the inner sort must be a stable algorithm. Counting sort is the standard choice. Swapping in an unstable inner sort (such as quicksort or heap sort) would break the relative order from previous passes, and the final array would not be sorted.

Good Use Cases

Poor Use Cases