How does Radix Sort work?

Radix Sort sorts numbers digit by digit, typically starting from the least significant digit (LSD) up to the most significant, using a stable sort like Counting Sort for each pass.

Base 10 vs Base 2 Radix Sort?

Base 10 is intuitive for decimals, while Base 2 (binary) is often more efficient for computer hardware. The choice of base affects the number of passes and bucket sizes.

Is Radix Sort faster than Merge Sort?

For large sets of integers with fixed digits, Radix Sort O(nk) can be faster than Merge Sort O(n log n), but it is limited to specific data types.

Radix Sort

Radix sort is a non-comparative sorting algorithm that processes the digits of numbers from least significant to most significant.

Intuition

Think of sorting a large pile of files by date (Year-Month-Day). You wouldn't compare every file to every other file. Instead, you would first sort them all into piles by Day (1-31). Then, stack them up and sort them again by Month (Jan-Dec). Finally, sort by Year. After this, the whole pile is perfectly sorted. This is Radix Sort: sorting column by column.

Concept

Radix sort never compares two elements. It sorts by one digit at a time, starting from the least significant, using a stable pass (usually counting sort) for each digit. Because every pass is stable, the order set by earlier digits survives the later ones, so once the most significant digit is done the whole array is sorted.

How it Works

Algorithm:

Find the maximum number to know the number of digits.
Do a stable sort (usually Counting Sort) for every digit place exp (1, 10, 100...).
Start from the Least Significant Digit (LSD).
Move to the next digit place and repeat.

Step-by-Step Breakdown

Watch the visualization:

Amber bar: The element whose digit at the current place (ones, tens, and so on) is being read, while counting and while moving it into place.
Red bar: The value being copied back into the array after a pass.
Green bars: The whole array, once the last digit place is done.
Passes: Each full sweep of the array represents sorting by one digit place.

When to Use

Fixed Length Keys: Like phone numbers, ID numbers, or integers where d (digits) is small.
Large Lists: Can be faster than Quick Sort (O(n)) when keys are short.

When NOT to Use

Variable Length Strings: Requires padding, which can waste space/time.
Space Limited: Requires auxiliary buffers for the buckets/counting sort step.

How to Identify

Look for "Sort an array of integers" where n is large (e.g., 10^5) but the range of values is constrained or comparable to n.

Sample Problems

Maximum Gap (LeetCode 164)

A classic hard problem specifically designed for Radix/Bucket sort (O(n) required).

Applying for software engineering roles? Free, no sign-up:

AI resume checker — match your resume to the job description

Counting Sort

Bucket Sort

Complexity

Time (Best)

O(N*k)

Time (Average)

O(N*k)

Time (Worst)

O(N*k)

Space

O(N + B)

Radix Sort Code

1function radixSort(arr) {
2    const max = Math.max(...arr);
3    for (let exp = 1; Math.floor(max / exp) > 0; exp *= 10) {
4        countSort(arr, exp);
5    }
6    return arr;
7}
8
9function countSort(arr, exp) {
10    const n = arr.length;
11    const output = new Array(n);
12    const count = new Array(10).fill(0);
13
14    for (let i = 0; i < n; i++) {
15        count[Math.floor(arr[i] / exp) % 10]++;
16    }
17    for (let i = 1; i < 10; i++) {
18        count[i] += count[i - 1];
19    }
20    for (let i = n - 1; i >= 0; i--) {
21        output[count[Math.floor(arr[i] / exp) % 10] - 1] = arr[i];
22        count[Math.floor(arr[i] / exp) % 10]--;
23    }
24    for (let i = 0; i < n; i++) {
25        arr[i] = output[i];
26    }
27}

Related Lessons

Radix Sort

Intuition

Concept

How it Works

Step-by-Step Breakdown

When to Use

When NOT to Use

How to Identify

Sample Problems

Maximum Gap (LeetCode 164)

AI resume checker — match your resume to the job description

Frequently Asked Questions

How does Radix Sort work?

Base 10 vs Base 2 Radix Sort?

Is Radix Sort faster than Merge Sort?