Offensive Security Researcher & Quantum Cryptography Analyst

Radix Sort Algorithm: A Linear-Time Integer Sorting Technique Explained

Abdul Wahab Junaid
Radix Sort A Linear-Time Integer Sorting Algorithm

I want to start with a simple question I asked myself when I first learned sorting algorithms: is it actually possible to sort a list faster than $O(n \log n)$? Every comparison-based algorithm I had studied up to that point — QuickSort, Merge Sort, Heap Sort — seemed to hit that same wall. Then I came across Radix Sort, and it changed how I thought about sorting entirely.

Radix Sort doesn’t compare elements against each other at all. Instead, it sorts numbers digit by digit, using a stable sorting subroutine (usually Counting Sort) as its engine. Because it sidesteps comparisons, it can sort in linear time under the right conditions. I find this a genuinely elegant idea, and in this article I want to walk through it the way I understood it myself — from history to implementation.

History and Background

The roots of Radix Sort go back further than computer science itself. I learned that the core idea traces back to punched card sorting machines used in the early 20th century, particularly Herman Hollerith’s tabulating machines from the 1890s, which processed census data using mechanical card sorters that worked digit by digit.

The algorithmic formalization I use today came later, with Harold H. Seward credited with describing the LSD (Least Significant Digit) Radix Sort in 1954 at MIT. Donald Knuth later documented and analyzed the algorithm thoroughly in The Art of Computer Programming, Volume 3: Sorting and Searching, which is where most modern treatments (including mine) draw their theoretical grounding.

What strikes me about this history is that Radix Sort predates electronic computers. The mechanical sorting machines that inspired it were literally physically sorting cards by punching patterns representing digits — a beautifully tactile origin for an algorithm I now think of as purely abstract.

Problem Statement

The problem I’m solving here is the same one every sorting algorithm addresses: given a list of $n$ elements, arrange them in non-decreasing (or non-increasing) order.

But Radix Sort is designed for a specific flavor of this problem: sorting integers (or fixed-length strings) where each element can be decomposed into a sequence of digits or characters. The comparison-based sorting lower bound tells me that any algorithm relying purely on comparisons cannot beat $O(n \log n)$ in the worst case. Radix Sort’s whole purpose is to escape that boundary by exploiting the structure of the keys themselves rather than comparing them pairwise.

Core Concepts

Before I get into the mechanics, I want to define the vocabulary I’ll be using:

How It Works

I use LSD Radix Sort in this article since it’s the most common variant and it’s what I implement below. Here is the step-by-step process I follow:

  1. Find the maximum number in the array to determine the number of digits I need to process.
  2. Starting with the least significant digit (units place), sort the entire array based on that digit using a stable sorting algorithm (I use Counting Sort).
  3. Move to the next digit (tens place) and sort the array again, but this time based on that digit — critically, using the already partially sorted array from the previous pass.
  4. Repeat this process for every digit position, up to the digit count of the largest number.
  5. Once I’ve processed the most significant digit, the array is fully sorted.

Working Principle

The internal logic here relies entirely on stability. Every single pass I make (one per digit) must preserve the relative order of elements that share the same digit value in the current position. If I use an unstable sort within each pass, previous work gets destroyed and the final result is wrong.

Here’s the intuition I hold onto: after I finish the pass on the units digit, the array is correctly sorted with respect to that digit — meaning any two elements with different units digits are in the right relative order. When I then sort on the tens digit, elements with the same tens digit need to retain their previous relative order (established by the units digit pass), which stability guarantees. By induction, after processing digit $k$, the array is correctly sorted considering only the last $k$ digits. Once $k$ equals the number of digits in the maximum element, the whole array is sorted.

Mathematical Foundation

If I have $n$ integers, each with $d$ digits, and each digit can take on $b$ possible values (the radix/base), then Radix Sort makes $d$ passes, and each pass involves a Counting Sort operation over $n$ elements with $b$ possible digit values.

The time complexity of a single Counting Sort pass is:

$$ O(n + b) $$

Since I perform this $d$ times, my total running time is:

$$ T(n) = O(d \cdot (n + b)) $$

If $b = O(n)$ and $d$ is treated as a constant (which is common when sorting fixed-width integers), this simplifies to:

$$ T(n) = O(n) $$

A useful way I think about $d$ is in terms of the maximum key value $k$ and the chosen base $b$:

$$ d = \log_b(k+1) $$

So the more precise running time, expressed in terms of $k$ and $b$, is:

$$ T(n) = O\left((n + b) \cdot \log_b(k+1)\right) $$

This formula tells me something important: choosing the base $b$ is a tuning decision. A larger base reduces the number of passes $d$ but increases the memory and per-pass cost from a larger bucket count $b$. Knuth’s analysis shows the optimal choice is often around $b \approx n$, balancing these two forces.

Diagrams

Here is a Mermaid diagram showing the overall pass-by-pass flow of LSD Radix Sort:

flowchart TD
    A[Unsorted Array] --> B[Find Maximum Element]
    B --> C[Determine Number of Digits d]
    C --> D[Set exp = 1]
    D --> E[Counting Sort on digit at exp]
    E --> F{exp * 10 less than or equal to max?}
    F -- Yes --> G[exp = exp * 10]
    G --> E
    F -- No --> H[Array is Fully Sorted]

And here is a diagram showing what happens inside a single Counting Sort digit-pass:

flowchart LR
    A[Input Array] --> B[Count occurrences of each digit 0-9]
    B --> C[Compute prefix sums of counts]
    C --> D[Place elements into output array right to left]
    D --> E[Copy output back into input array]

Pseudocode

Here is the language-independent pseudocode I follow:

RADIX-SORT(A, n)
    max = MAXIMUM(A, n)
    exp = 1
    while max / exp > 0
        COUNTING-SORT-BY-DIGIT(A, n, exp)
        exp = exp * 10

COUNTING-SORT-BY-DIGIT(A, n, exp)
    output = new array of size n
    count = new array of size 10, initialized to 0

    for i = 0 to n - 1
        digit = (A[i] / exp) mod 10
        count[digit] = count[digit] + 1

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

    for i = n - 1 down to 0
        digit = (A[i] / exp) mod 10
        output[count[digit] - 1] = A[i]
        count[digit] = count[digit] - 1

    copy output into A

Step-by-Step Example

Let me walk through a concrete example using the array:

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

Step 1 — Sort by units digit (exp = 1):

Digits: 0, 5, 5, 0, 2, 4, 2, 6

Result after this pass: $$ [170, 90, 802, 2, 24, 45, 75, 66] $$

Step 2 — Sort by tens digit (exp = 10):

Digits: 7, 9, 0, 0, 2, 4, 7, 6

Result after this pass: $$ [802, 2, 24, 45, 66, 170, 75, 90] $$

Step 3 — Sort by hundreds digit (exp = 100):

Digits: 8, 0, 0, 0, 0, 1, 0, 0

Result after this final pass: $$ [2, 24, 45, 66, 75, 90, 170, 802] $$

The array is now fully sorted, and this matches exactly what my tested C implementation produces.

Time Complexity

This uniformity is actually one of Radix Sort’s more interesting properties to me: unlike QuickSort, whose worst case diverges wildly from its average case, Radix Sort’s performance is remarkably predictable.

Space Complexity

I need auxiliary space for:

So the space complexity is:

$$ O(n + b) $$

This is not in-place, which I consider one of its genuine downsides compared to something like Heap Sort.

Correctness Analysis

I rely on a simple inductive argument to convince myself Radix Sort is correct.

Claim: After processing the first $k$ least-significant digits, the array is sorted correctly with respect to those $k$ digits (i.e., as if those $k$ digits were the entire number).

Base case: After processing 0 digits, the claim holds trivially.

Inductive step: Assume the array is correctly sorted with respect to the least significant $k$ digits. When I sort by digit $k+1$ using a stable sort, elements with equal $(k+1)$-th digits retain their relative order from the previous step — which was already correct for the lower $k$ digits. Elements with different $(k+1)$-th digits get properly separated. Therefore, the array is now correctly sorted with respect to $k+1$ digits.

By induction, once $k$ equals $d$ (the maximum digit count), the array is fully and correctly sorted. The load-bearing requirement throughout this proof is stability — without it, the induction breaks at the very first step.

Advantages

Disadvantages

Applications

I’ve seen Radix Sort used in a range of practical contexts:

Implementation in C

Here is my full working implementation, which I compiled and tested:

#include <stdio.h>
#include <stdlib.h>

// Returns the maximum value in the array so we know how many digits to process
int getMax(int arr[], int n) {
    int max = arr[0];
    for (int i = 1; i < n; i++)
        if (arr[i] > max)
            max = arr[i];
    return max;
}

// A stable Counting Sort that sorts arr[] according to the digit
// represented by exp (exp = 1 for units, 10 for tens, 100 for hundreds, etc.)
void countingSortByDigit(int arr[], int n, int exp) {
    int output[n];
    int count[10] = {0};

    // Count occurrences of each digit
    for (int i = 0; i < n; i++)
        count[(arr[i] / exp) % 10]++;

    // Turn counts into prefix sums (positions in output)
    for (int i = 1; i < 10; i++)
        count[i] += count[i - 1];

    // Build the output array, iterating backwards to preserve stability
    for (int i = n - 1; i >= 0; i--) {
        int digit = (arr[i] / exp) % 10;
        output[count[digit] - 1] = arr[i];
        count[digit]--;
    }

    // Copy the sorted output back into the original array
    for (int i = 0; i < n; i++)
        arr[i] = output[i];
}

// Main Radix Sort driver: repeatedly sorts by each digit from LSD to MSD
void radixSort(int arr[], int n) {
    int max = getMax(arr, n);

    // exp represents the digit position: 1, 10, 100, ...
    for (int exp = 1; max / exp > 0; exp *= 10)
        countingSortByDigit(arr, n, exp);
}

void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

int main() {
    int arr[] = {170, 45, 75, 90, 802, 24, 2, 66};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("Before sorting: ");
    printArray(arr, n);

    radixSort(arr, n);

    printf("After sorting:  ");
    printArray(arr, n);

    return 0;
}

Sample Input and Output

Input:

170 45 75 90 802 24 2 66

Output (verified by compiling and running the code above):

Before sorting: 170 45 75 90 802 24 2 66 
After sorting:  2 24 45 66 75 90 170 802

Optimization Techniques

A few techniques I keep in mind when I want to squeeze more performance out of Radix Sort:

Common Mistakes

Mistakes I’ve seen (and made) while implementing this algorithm:

Further Reading

Exit mobile version