Radix Sort Algorithm Explained

Radix Sort is a non-comparison sorting algorithm that sorts numbers digit by digit. Instead of comparing elements directly, it processes each digit position, starting from the least significant digit or the most significant digit, and uses a stable sorting method to organize the numbers at each step.

Radix Sort is powerful when sorting integers with a limited number of digits. It is closely connected to Counting Sort because Counting Sort is commonly used as the stable subroutine for sorting numbers by each digit.

Introduction

Most sorting algorithms compare values with each other. Bubble Sort compares neighbors, Selection Sort finds the smallest element, Insertion Sort inserts values into the correct position, and Quicksort partitions values around a pivot.

Radix Sort uses a different strategy. It does not compare full numbers directly. Instead, it looks at individual digits and sorts the numbers one digit position at a time.

This makes Radix Sort an important algorithm because it shows that sorting can sometimes be done without traditional comparisons. When the data is suitable, Radix Sort can be very efficient and can achieve linear-like performance.

What Is Radix Sort?

Radix Sort is a sorting algorithm that sorts numbers by processing their digits. The word “radix” refers to the base of the number system. In the decimal system, the radix is 10 because digits range from 0 to 9.

For example, the number 472 has three digit positions:

  • Ones digit: 2

  • Tens digit: 7

  • Hundreds digit: 4

Radix Sort can sort a list of numbers by first sorting according to the ones digit, then the tens digit, then the hundreds digit, and so on.

The main idea is simple:

  • Find the maximum number to know how many digit positions are needed.

  • Sort the array by the ones digit.

  • Sort the array by the tens digit.

  • Sort the array by the hundreds digit.

  • Continue until all digit positions are processed.

After all digit positions are processed using a stable sorting method, the array becomes fully sorted.

Why Radix Sort Needs a Stable Sort

Radix Sort depends on stability. A stable sorting algorithm preserves the relative order of elements with equal keys.

This is important because Radix Sort sorts one digit at a time. When sorting by a later digit, the order created by previous digit sorting must not be destroyed.

For example, if two numbers have the same tens digit, their previous order from the ones digit sorting should remain unchanged. Without stability, the digit-by-digit process may produce an incorrect final result.

This is why Counting Sort is commonly used inside Radix Sort. Stable Counting Sort can sort values by a specific digit while preserving the order of numbers that have the same digit.

LSD Radix Sort and MSD Radix Sort

There are two common approaches to Radix Sort: LSD Radix Sort and MSD Radix Sort.

LSD Radix Sort means Least Significant Digit Radix Sort. It starts from the rightmost digit, such as the ones digit, then moves left to the tens, hundreds, thousands, and higher positions.

MSD Radix Sort means Most Significant Digit Radix Sort. It starts from the leftmost digit and moves toward the right.

This article focuses on LSD Radix Sort because it is easier to understand and commonly taught when explaining Radix Sort with Counting Sort.

How LSD Radix Sort Works

LSD Radix Sort processes numbers from the least significant digit to the most significant digit. In decimal numbers, this means starting with the ones digit, then tens digit, then hundreds digit, and so on.

The algorithm works like this:

  1. Find the maximum value in the array.

  2. Start with the digit position 1, which represents the ones digit.

  3. Sort all numbers by the current digit using a stable sorting algorithm.

  4. Move to the next digit position by multiplying the place value by 10.

  5. Repeat until the maximum number has no more digits to process.

The key point is that each digit-level sorting step must be stable.

Manual Run Example

Let us manually sort the following array using LSD Radix Sort:

[170, 45, 75, 90, 802, 24, 2, 66]

The maximum value is:

802

Since 802 has three digits, Radix Sort will process three digit positions:

  • Ones digit

  • Tens digit

  • Hundreds digit

Pass 1: Sort by Ones Digit

First, we sort the numbers by their ones digit.

Number: 170  Ones digit: 0
Number: 45   Ones digit: 5
Number: 75   Ones digit: 5
Number: 90   Ones digit: 0
Number: 802  Ones digit: 2
Number: 24   Ones digit: 4
Number: 2    Ones digit: 2
Number: 66   Ones digit: 6

Now we group numbers by ones digit while preserving their relative order:

Digit 0: 170, 90
Digit 1:
Digit 2: 802, 2
Digit 3:
Digit 4: 24
Digit 5: 45, 75
Digit 6: 66
Digit 7:
Digit 8:
Digit 9:

After sorting by the ones digit, the array becomes:

[170, 90, 802, 2, 24, 45, 75, 66]

This array is not fully sorted yet. It is only sorted according to the ones digit.

Pass 2: Sort by Tens Digit

Now we sort the current array by the tens digit.

Current array:
[170, 90, 802, 2, 24, 45, 75, 66]

The tens digits are:

Number: 170  Tens digit: 7
Number: 90   Tens digit: 9
Number: 802  Tens digit: 0
Number: 2    Tens digit: 0
Number: 24   Tens digit: 2
Number: 45   Tens digit: 4
Number: 75   Tens digit: 7
Number: 66   Tens digit: 6

Now we group numbers by tens digit while preserving order:

Digit 0: 802, 2
Digit 1:
Digit 2: 24
Digit 3:
Digit 4: 45
Digit 5:
Digit 6: 66
Digit 7: 170, 75
Digit 8:
Digit 9: 90

After sorting by the tens digit, the array becomes:

[802, 2, 24, 45, 66, 170, 75, 90]

The array is still not fully sorted, but it now respects the order of ones and tens digits together because stable sorting preserved the previous pass.

Pass 3: Sort by Hundreds Digit

Now we sort the current array by the hundreds digit.

Current array:
[802, 2, 24, 45, 66, 170, 75, 90]

The hundreds digits are:

Number: 802  Hundreds digit: 8
Number: 2    Hundreds digit: 0
Number: 24   Hundreds digit: 0
Number: 45   Hundreds digit: 0
Number: 66   Hundreds digit: 0
Number: 170  Hundreds digit: 1
Number: 75   Hundreds digit: 0
Number: 90   Hundreds digit: 0

Now we group numbers by hundreds digit while preserving order:

Digit 0: 2, 24, 45, 66, 75, 90
Digit 1: 170
Digit 2:
Digit 3:
Digit 4:
Digit 5:
Digit 6:
Digit 7:
Digit 8: 802
Digit 9:

After sorting by the hundreds digit, the array becomes:

[2, 24, 45, 66, 75, 90, 170, 802]

Final Sorted Array

[2, 24, 45, 66, 75, 90, 170, 802]

This manual run shows how Radix Sort gradually builds the final order. Each pass sorts by one digit position, and stability ensures that previous digit ordering remains correct.

How to Extract a Digit

Radix Sort needs a way to extract a specific digit from a number. For decimal numbers, we can use division and modulo operations.

To extract a digit at a specific place value:

digit = Math.floor(number / place) % 10

For example, for the number 170:

  • Ones digit: Math.floor(170 / 1) % 10 = 0

  • Tens digit: Math.floor(170 / 10) % 10 = 7

  • Hundreds digit: Math.floor(170 / 100) % 10 = 1

In PHP, the same idea can be written as:

$digit = intdiv($number, $place) % 10;

The place value starts at 1 and is multiplied by 10 after each pass.

Radix Sort Algorithm Steps

The LSD Radix Sort algorithm can be described using these steps:

  1. Find the maximum value in the input array.

  2. Set the initial place value to 1.

  3. Use a stable sorting algorithm to sort the array by the digit at the current place value.

  4. Multiply the place value by 10.

  5. Repeat while the maximum value divided by the place value is greater than 0.

  6. Return the sorted array.

Counting Sort is usually used as the stable digit-sorting algorithm because each digit is between 0 and 9.

Pseudocode

radixSort(array):
    max = find maximum value in array
    place = 1

    while max / place > 0:
        countingSortByDigit(array, place)
        place = place * 10

    return array

The helper function sorts the array according to one digit position:

countingSortByDigit(array, place):
    count = array of size 10 filled with 0
    output = array of same size as input

    for each number in array:
        digit = (number / place) % 10
        count[digit] = count[digit] + 1

    for i from 1 to 9:
        count[i] = count[i] + count[i - 1]

    for i from length(array) - 1 down to 0:
        digit = (array[i] / place) % 10
        position = count[digit] - 1
        output[position] = array[i]
        count[digit] = count[digit] - 1

    copy output back to array

The helper function is a stable Counting Sort applied to one digit position.

Radix Sort Example in PHP

Here is a clean PHP implementation of Radix Sort for non-negative integers:

<?php

function radixSort(array $numbers): array
{
    if ($numbers === []) {
        return [];
    }

    $max = max($numbers);

    for ($place = 1; intdiv($max, $place) > 0; $place *= 10) {
        $numbers = countingSortByDigit($numbers, $place);
    }

    return $numbers;
}

function countingSortByDigit(array $numbers, int $place): array
{
    $length = count($numbers);
    $output = array_fill(0, $length, 0);
    $count = array_fill(0, 10, 0);

    foreach ($numbers as $number) {
        $digit = intdiv($number, $place) % 10;
        $count[$digit]++;
    }

    for ($i = 1; $i < 10; $i++) {
        $count[$i] += $count[$i - 1];
    }

    for ($i = $length - 1; $i >= 0; $i--) {
        $digit = intdiv($numbers[$i], $place) % 10;
        $position = $count[$digit] - 1;

        $output[$position] = $numbers[$i];
        $count[$digit]--;
    }

    return $output;
}

$numbers = [170, 45, 75, 90, 802, 24, 2, 66];

print_r(radixSort($numbers));

The output will be:

Array
(
    [0] => 2
    [1] => 24
    [2] => 45
    [3] => 66
    [4] => 75
    [5] => 90
    [6] => 170
    [7] => 802
)

This implementation uses stable Counting Sort for each digit position. The count array has only 10 positions because decimal digits range from 0 to 9.

Radix Sort Example in JavaScript

Here is the same algorithm implemented in JavaScript:

function radixSort(numbers) {
    if (numbers.length === 0) {
        return [];
    }

    const max = Math.max(...numbers);

    for (let place = 1; Math.floor(max / place) > 0; place *= 10) {
        numbers = countingSortByDigit(numbers, place);
    }

    return numbers;
}

function countingSortByDigit(numbers, place) {
    const output = new Array(numbers.length);
    const count = new Array(10).fill(0);

    for (const number of numbers) {
        const digit = Math.floor(number / place) % 10;
        count[digit]++;
    }

    for (let i = 1; i < 10; i++) {
        count[i] += count[i - 1];
    }

    for (let i = numbers.length - 1; i >= 0; i--) {
        const digit = Math.floor(numbers[i] / place) % 10;
        const position = count[digit] - 1;

        output[position] = numbers[i];
        count[digit]--;
    }

    return output;
}

const numbers = [170, 45, 75, 90, 802, 24, 2, 66];

console.log(radixSort(numbers));

The output will be:

[2, 24, 45, 66, 75, 90, 170, 802]

The JavaScript version follows the same logic as the PHP version. It repeatedly sorts by digit position using a stable Counting Sort helper.

Why Counting Sort Is Used Inside Radix Sort

Counting Sort is a good helper for Radix Sort because each digit has a small fixed range. In decimal numbers, each digit can only be between 0 and 9.

This means the count array always has size 10 for each digit pass:

Digit values: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9

Because the digit range is small, Counting Sort becomes very efficient inside Radix Sort.

Counting Sort also provides stability when implemented with cumulative counts. This stability is necessary for Radix Sort to produce the correct final order.

Time Complexity of Radix Sort

Time complexity describes how the running time of an algorithm grows as the input size increases. Radix Sort depends on the number of elements, the number of digit positions, and the base or range used for each digit.

The standard time complexity of Radix Sort is:

O(d × (n + k))

Where:

  • n is the number of elements.

  • d is the number of digit positions.

  • k is the range of possible digit values.

In decimal LSD Radix Sort, k is usually 10 because digits range from 0 to 9.

So for decimal numbers, this is often written as:

O(d × n)

This simplified form is used when k is treated as a constant.

Why Radix Sort Is O(d × (n + k))

For each digit position, Radix Sort performs a stable Counting Sort.

Counting Sort by digit takes:

O(n + k)

If the largest number has d digits, the algorithm repeats this process d times.

Therefore, the total time complexity becomes:

O(d × (n + k))

If k is fixed at 10, the formula becomes close to:

O(d × n)

If d is also small and limited, Radix Sort can behave close to linear time.

Best Case Time Complexity

The best case time complexity of Radix Sort is:

O(d × (n + k))

Radix Sort still needs to process every digit position even if the input array is already sorted. Unlike Insertion Sort, it does not become O(n) just because the data is already ordered.

Average Case Time Complexity

The average case time complexity is also:

O(d × (n + k))

The algorithm follows the same digit-by-digit process regardless of the original order of the input.

Worst Case Time Complexity

The worst case time complexity is:

O(d × (n + k))

This is because Radix Sort does not depend on bad pivots or reversed arrays. Its performance depends mainly on the number of digits and the digit range.

However, if the numbers have many digits, d becomes large. In that case, Radix Sort may become less practical.

Space Complexity of Radix Sort

Radix Sort usually requires extra memory because stable Counting Sort uses an output array and a count array.

The space complexity is:

O(n + k)

Where n is the number of elements and k is the digit range.

For decimal digits, k is 10, so the main extra memory comes from the output array of size n.

Because of this, Radix Sort is generally not considered an in-place sorting algorithm in its common stable implementation.

Is Radix Sort Stable?

Radix Sort is stable if the internal digit-sorting algorithm is stable.

When LSD Radix Sort uses stable Counting Sort, the full algorithm becomes stable. This means equal values keep their relative order.

If the internal sorting step is not stable, Radix Sort may fail because later digit passes can destroy the ordering created by earlier digit passes.

So the correct answer is:

  • Radix Sort with stable Counting Sort: stable.

  • Radix Sort with unstable digit sorting: not guaranteed to be stable.

Is Radix Sort a Comparison-Based Algorithm?

Radix Sort is not a comparison-based sorting algorithm. It does not sort by repeatedly comparing elements with each other.

Instead, it uses digit extraction and stable distribution. This is why Radix Sort can sometimes perform faster than comparison-based algorithms under the right conditions.

Comparison-based sorting algorithms have a lower bound of O(n log n) for general sorting. Radix Sort avoids this limitation by using assumptions about the data, such as numeric digit structure and limited digit range.

Radix Sort vs Counting Sort

Counting Sort and Radix Sort are closely related, but they are not the same.

Counting Sort counts full values directly. It works well when the complete value range is small. For example, sorting exam scores from 0 to 100 is a good Counting Sort use case.

Radix Sort sorts values digit by digit. It is useful when the complete value range may be large, but each digit has a small range.

  • Counting Sort uses the whole value as an index.

  • Radix Sort uses one digit at a time.

  • Counting Sort has time complexity O(n + k).

  • Radix Sort has time complexity O(d × (n + k)).

  • Counting Sort is simpler.

  • Radix Sort can handle larger numbers more efficiently than direct Counting Sort when the range is huge.

In practice, Radix Sort often uses Counting Sort internally.

Radix Sort vs Quicksort

Quicksort is a comparison-based sorting algorithm. It works by selecting a pivot and partitioning the array around that pivot.

Radix Sort is a non-comparison algorithm. It sorts values by digit positions.

  • Quicksort average time complexity is O(n log n).

  • Radix Sort time complexity is O(d × (n + k)).

  • Quicksort works for many comparable data types.

  • Radix Sort works best for integers or fixed-length keys.

  • Quicksort can be in-place.

  • Radix Sort usually needs extra memory.

Quicksort is more general. Radix Sort is more specialized, but it can be very fast when the data matches its assumptions.

Radix Sort vs Merge Sort

Merge Sort is a stable comparison-based sorting algorithm with guaranteed O(n log n) time complexity. Radix Sort is non-comparison-based and can be faster for suitable integer data.

The main differences are:

  • Merge Sort compares elements.

  • Radix Sort processes digits.

  • Merge Sort works for general comparable values.

  • Radix Sort works best for integers or fixed-size keys.

  • Merge Sort has O(n log n) time complexity.

  • Radix Sort has O(d × (n + k)) time complexity.

  • Both usually require extra memory.

Merge Sort is more general and predictable. Radix Sort is more data-specific and can be faster when the number of digits is limited.

Handling Numbers with Different Lengths

Radix Sort can handle numbers with different digit lengths. Shorter numbers are treated as if they have leading zeros.

For example:

2 can be treated as 002
24 can be treated as 024
802 stays as 802

This is why, during the hundreds digit pass, numbers like 2, 24, 45, and 90 have a hundreds digit of 0.

The algorithm does not need to physically add zeros. Digit extraction naturally returns 0 when the place value is larger than the number.

Handling Negative Numbers

The basic Radix Sort implementation usually works with non-negative integers. Negative numbers require additional handling because digit extraction and ordering become more complex.

A common approach is:

  1. Separate negative numbers and non-negative numbers.

  2. Convert negative numbers to positive values temporarily.

  3. Sort both groups separately.

  4. Reverse the sorted negative group.

  5. Convert negative values back.

  6. Combine negatives first, then non-negative numbers.

For example:

Input: [-10, 5, -3, 2]

Negatives as positive: [10, 3]
Sorted positives from negatives: [3, 10]
Reverse and restore signs: [-10, -3]

Non-negatives sorted: [2, 5]

Final result: [-10, -3, 2, 5]

This additional logic is necessary because normal digit-by-digit sorting assumes non-negative values.

Practical Example: Sorting Student IDs

Radix Sort is useful when sorting numeric IDs that have a limited number of digits.

Student IDs:
[1203, 1045, 1002, 1320, 1111]

All IDs have four digits. Radix Sort can sort them digit by digit:

Sorted IDs:
[1002, 1045, 1111, 1203, 1320]

This kind of data is a good fit because each number has a predictable digit structure.

Practical Example: Sorting Product Codes

If product codes are numeric, Radix Sort can be used to sort them efficiently.

Product codes:
[501, 120, 305, 220, 110]

After Radix Sort:

[110, 120, 220, 305, 501]

However, if product codes contain letters, symbols, or mixed formats, the algorithm needs mapping or a different approach.

When Should Developers Use Radix Sort?

Developers should consider Radix Sort when the data fits the algorithm's assumptions.

Radix Sort is useful when:

  • The values are non-negative integers.

  • The number of digits is limited.

  • The digit range is small.

  • Stable sorting is useful.

  • The input size is large enough to benefit from linear-like behavior.

  • The data uses fixed-length numeric keys such as IDs or codes.

When these conditions are true, Radix Sort can be very efficient.

When Not to Use Radix Sort

Radix Sort is not always the best choice.

Developers should avoid Radix Sort when:

  • The data is not numeric or cannot be mapped cleanly to digits.

  • The numbers have too many digits.

  • Memory usage must be very low.

  • The dataset is small and a built-in sort is simpler.

  • The implementation would become more complex than the problem requires.

  • The sorting key is a complex object comparison.

In many real applications, built-in sorting functions are easier, safer, and highly optimized. Radix Sort is most useful when its assumptions match the data very well.

Common Mistakes When Implementing Radix Sort

Radix Sort has more moving parts than simple algorithms, so beginners often make mistakes in digit extraction, loop conditions, or stability.

Common mistakes include:

  • Using an unstable sorting method for each digit pass.

  • Forgetting to process all digit positions.

  • Extracting the wrong digit.

  • Using the wrong loop condition for the maximum value.

  • Ignoring numbers with different digit lengths.

  • Trying to sort negative numbers without extra handling.

  • Confusing Radix Sort with Counting Sort.

  • Forgetting that the count array for decimal digits should have 10 positions.

The most important mistake is ignoring stability. Without stable digit sorting, LSD Radix Sort may produce incorrect results.

Practical Checklist for Understanding Radix Sort

Before moving to more advanced sorting algorithms, developers should be able to answer these questions:

  • What does radix mean?

  • What is the difference between LSD and MSD Radix Sort?

  • Why does LSD Radix Sort start from the ones digit?

  • Why does Radix Sort need stable sorting?

  • How does Counting Sort help Radix Sort?

  • How do we extract a digit from a number?

  • Why is the time complexity O(d × (n + k))?

  • Why is Radix Sort not usually in-place?

  • When is Radix Sort better than comparison-based sorting?

If these questions are clear, the developer understands the real logic behind Radix Sort instead of only memorizing code.

Advantages of Radix Sort

Radix Sort has several advantages when used with suitable data.

  • It can be faster than O(n log n) comparison-based algorithms in suitable cases.

  • It does not rely on direct element comparisons.

  • It works well for integers with limited digit length.

  • It can be stable when implemented with stable Counting Sort.

  • It is useful for sorting IDs, codes, and fixed-length numeric keys.

  • It teaches important ideas such as digit processing and stable sub-sorting.

These advantages make Radix Sort an important algorithm in data structures and algorithms education.

Disadvantages of Radix Sort

Radix Sort also has important limitations.

  • It is not a general-purpose sorting algorithm for all data types.

  • It usually requires extra memory.

  • It is more complex than simple sorting algorithms.

  • It requires special handling for negative numbers.

  • It may not be efficient when numbers have many digits.

  • It depends on a stable internal sorting algorithm.

Radix Sort is powerful, but only when the data structure and value format are suitable.

Conclusion

Radix Sort is a non-comparison sorting algorithm that sorts numbers digit by digit. In LSD Radix Sort, the algorithm starts from the least significant digit and moves toward the most significant digit.

The algorithm commonly uses stable Counting Sort as a helper for each digit position. Stability is essential because each pass must preserve the order created by previous digit passes.

The time complexity of Radix Sort is O(d × (n + k)), where n is the number of elements, d is the number of digit positions, and k is the digit range. For decimal numbers, k is usually 10, which makes Radix Sort efficient when the number of digits is limited.

Radix Sort is not always the best choice for every problem. It requires extra memory, works best with non-negative integers, and needs additional logic for negative numbers or complex data types.

For developers learning algorithms, Radix Sort is valuable because it introduces a different way of thinking about sorting. Instead of comparing full values, it uses digits, stable sorting, and repeated passes to produce a fully sorted result. Understanding Radix Sort also strengthens the developer's understanding of Counting Sort, stability, and non-comparison-based algorithms.