Radix Sort is a non-comparison-based sorting algorithm that processes elements digit by digit, starting from the least significant digit to the most significant (or vice versa). Instead of comparing values directly, it groups elements based on their digits at each position.

At each step, a stable sorting algorithm like Counting Sort is used to reorder the elements according to the current digit. By repeating this process across all digits, the array becomes fully sorted.

Radix Sort achieves linear time complexity O(n · d), where d is the number of digits, making it efficient for sorting large sets of integers or strings with fixed length.

In this chapter, you will learn how Radix Sort works step by step, how it builds on Counting Sort, and when it is a better choice than 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:

The key insight is that 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. This is critical. Without stability, sorting by the tens digit would destroy the ordering we established when sorting by the ones digit. Counting sort is the standard choice for this subroutine because it is stable, runs in O(n + k) time, and works perfectly 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

To isolate the digit at a given position, we use 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?

This is the part that trips people up. How can sorting by the least significant digit first produce a correct result?

The answer is stability. When we sort by the ones digit, all numbers with the same ones digit are grouped together. When we then sort by the tens digit, numbers with the same tens digit are grouped, but within each group, the relative order from the ones-digit pass is preserved. By the time we reach the most significant digit, each pass has refined the ordering, and stability ensures that earlier passes are never undone.

Think of it like sorting a spreadsheet. If you sort 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. That is exactly what LSD radix sort does with digit positions.

Counting Sort as Subroutine

Before implementing radix sort, we need 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 we are sorting by (1 for ones, 10 for tens, 100 for hundreds).

Let us trace through the algorithm with the array [170, 45, 75, 90, 802, 24, 2, 66].

First, we find the maximum value: 802. It has 3 digits, so we need 3 passes.

Pass 1: Sort by Ones Digit (exp = 1)

We extract the ones digit of each number using (num / 1) % 10:

After counting sort by the ones digit:

Notice that 170 appears before 90 (both have ones digit 0) because 170 came first in the original array. Similarly, 802 appears before 2. Stability at work.

Pass 2: Sort by Tens Digit (exp = 10)

We extract the tens digit using (num / 10) % 10:

After counting sort by the tens digit:

802 and 2 both have tens digit 0. In the previous pass, 802 came before 2. Stability preserves this order. Similarly, 170 appears before 75 (both have tens digit 7).

Pass 3: Sort by Hundreds Digit (exp = 100)

We extract the hundreds digit using (num / 100) % 10:

After counting sort by the hundreds digit:

All the numbers with hundreds digit 0 retain their relative order from the previous pass: 2, 24, 45, 66, 75, 90. That order was correct because the previous two passes already sorted them by their tens and ones digits. The array is now fully sorted.

Where:

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

For radix sort to beat comparison-based sorts, we need 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 would be faster.

The takeaway: radix sort shines when the number of digits is small and the dataset is large.

Good Use Cases

Poor Use Cases