Radix Sort Algorithm

The radix sort algorithm sorts numbers one digit at a time, starting from the ones digit, using a stable bucket pass for each digit. For fixed-length keys it runs in linear time without comparing elements. Step through it below, then read how it works.

What is Radix Sort?

Radix Sort (LSD) sorts numbers digit by digit, starting from the least significant digit. For each digit it performs a stable sort (usually Counting Sort), so earlier digits stay ordered when later digits tie.

Key insight: Stability is what makes it work: sorting by the ones digit, then tens, then hundreds leaves the list fully ordered because each pass keeps the order produced by the previous one.

Radix Sort Time Complexity

Measure	Value
Best case	O(d(n + b))
Average case	O(d(n + b))
Worst case	O(d(n + b))
Space	O(n + b)
Stable	Yes

For a formal definition and complexity analysis, see the NIST Dictionary of Algorithms and Data Structures entry for radix sort.

Algorithm Steps

1. Find the maximum number to know how many digits (d) there are.
2. Starting with the ones digit, distribute the numbers into 10 buckets by that digit.
3. Collect the buckets in order 0 to 9, keeping the order inside each bucket.
4. Repeat for the tens, hundreds and so on.
5. After the last digit, the list is sorted.

Advantages and Disadvantages

Advantages

• Linear time for fixed-width keys: O(d(n + b))
• Stable
• Can outperform comparison sorts on large integer data

Disadvantages

• Needs extra memory for buckets and output
• Only works for keys that can be split into digits or characters
• Slower than expected when numbers have many digits

Real-World Applications

• Sorting large sets of integers or fixed-length keys (IDs, phone numbers, dates)
• Sorting strings of equal length
• Parallel and GPU sorting
• Suffix array construction and other string algorithms

When to Use Radix Sort

Use it for many integers or fixed-length keys with a limited number of digits. For general objects or unbounded keys, comparison sorts are simpler.

Radix Sort Implementation

Python

def counting_by_digit(arr, exp):
    out = [0] * len(arr)
    count = [0] * 10
    for x in arr:
        count[(x // exp) % 10] += 1
    for i in range(1, 10):
        count[i] += count[i - 1]
    for x in reversed(arr):             # stable
        d = (x // exp) % 10
        count[d] -= 1
        out[count[d]] = x
    return out

def radix_sort(arr):
    if not arr:
        return arr
    exp = 1
    while max(arr) // exp > 0:
        arr = counting_by_digit(arr, exp)
        exp *= 10
    return arr

JavaScript

function countingByDigit(arr, exp) {
  const out = new Array(arr.length);
  const count = new Array(10).fill(0);
  for (const x of arr) count[Math.floor(x / exp) % 10]++;
  for (let i = 1; i < 10; i++) count[i] += count[i - 1];
  for (let i = arr.length - 1; i >= 0; i--) {       // stable
    const d = Math.floor(arr[i] / exp) % 10;
    out[--count[d]] = arr[i];
  }
  return out;
}

function radixSort(arr) {
  if (arr.length === 0) return arr;
  const max = Math.max(...arr);
  for (let exp = 1; Math.floor(max / exp) > 0; exp *= 10) {
    arr = countingByDigit(arr, exp);
  }
  return arr;
}

FAQ

Why must each digit pass be stable?

Sorting by the tens digit must not undo the order already established by the ones digit. A stable pass keeps numbers with the same tens digit in their ones-digit order, which is what makes the final result fully sorted.

What is the difference between LSD and MSD radix sort?

LSD (least significant digit, shown here) processes the ones digit first and works on whole lists each round. MSD starts from the most significant digit and recursively sorts each bucket, which suits variable-length keys such as strings.

When is radix sort better than quick sort?

When keys are integers or fixed-length strings with few digits, such as IDs, ZIP codes or 32-bit integers, radix sort can beat comparison sorts like Quick Sort. For general data or wide keys, comparison sorts are usually simpler and as fast.

---

More Sorting Algorithms

• Counting Sort
• Quick Sort
• Merge Sort
• Timsort