Radix Sort is a non-comparison sorting algorithm — it never compares two elements directly. Instead, it sorts by processing individual digits, one digit position at a time from least significant to most significant (LSD approach). This lets it sort integers in O(n) time for a fixed number of digits, breaking the O(n log n) lower bound that applies to comparison-based sorts.

Key Idea — Sort Digit by Digit

Radix Sort uses a stable subroutine (counting sort) on each digit position. Because counting sort is stable, equal digits preserve the relative order established by previous passes. After processing every digit position, the array is fully sorted.

Step-by-Step Example

Sort [170, 45, 75, 90, 2, 802]:

Initial:         [170,  45,  75,  90,   2, 802]

Pass 1 — ones digit (exp=1):
  digits:          0    5    5    0    2    2
  After sort:  [170,  90,   2, 802,  45,  75]

Pass 2 — tens digit (exp=10):
  digits:          7    9    0    0    4    7
  After sort:  [  2, 802,  45, 170,  75,  90]

Pass 3 — hundreds digit (exp=100):
  digits:          0    8    0    1    0    0
  After sort:  [  2,  45,  75,  90, 170, 802]

Sorted: [2, 45, 75, 90, 170, 802] ✓

Notice that after Pass 1, the two numbers ending in 5 (45 and 75) retain their original order — counting sort is stable, which is what makes the whole algorithm work correctly.

How Counting Sort Works (the subroutine)

For each digit pass, counting sort runs in three steps:

1. Count — count how many numbers have each digit value (0–9)
2. Cumulate — convert counts to starting positions using prefix sums
3. Place — iterate the input backwards (to preserve stability) and place each element at its computed position in the output array

C Program — Radix Sort

#include <stdio.h>

#define MAX 100

/* Stable counting sort on the digit at position exp (1, 10, 100, ...) */
void counting_sort(int arr[], int n, int exp) {
    int output[MAX];
    int count[10] = {0};

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

    /* Step 2: cumulative sum — count[i] now holds the end position of digit i */
    for (int i = 1; i < 10; i++)
        count[i] += count[i - 1];

    /* Step 3: place elements (iterate backwards to keep sort stable) */
    for (int i = n - 1; i >= 0; i--) {
        int digit = (arr[i] / exp) % 10;
        output[--count[digit]] = arr[i];
    }

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

void radix_sort(int arr[], int n) {
    /* Find the maximum element to determine number of digit passes */
    int max = arr[0];
    for (int i = 1; i < n; i++)
        if (arr[i] > max)
            max = arr[i];

    /* Run counting sort for each digit position: 1, 10, 100, ... */
    for (int exp = 1; max / exp > 0; exp *= 10)
        counting_sort(arr, n, exp);
}

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

int main(void) {
    int n;
    printf("Enter number of elements: ");
    scanf("%d", &n);

    int arr[n];
    printf("Enter %d elements: ", n);
    for (int i = 0; i < n; i++)
        scanf("%d", &arr[i]);

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

    radix_sort(arr, n);

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

    return 0;
}

Code Explanation

• (arr[i] / exp) % 10 — extracts the digit at the current position. exp=1 gives the ones digit, exp=10 gives the tens digit, and so on.
• Cumulative sum — after count[i] += count[i-1], count[d] holds the index just past where the last element with digit d should be placed.
• Backwards iteration — iterating i from n-1 to 0 in Step 3 preserves the relative order of elements with the same digit (stability). If you iterate forwards, equal-digit elements end up reversed.
• Outer loop stops when max / exp == 0 — no more digit positions to process beyond the most significant digit of the maximum value.

Sample Output

Enter number of elements: 6
Enter 6 elements: 170 45 75 90 2 802
Before sorting: 170 45 75 90 2 802
After sorting:  2 45 75 90 170 802

Time and Space Complexity

Where d = number of digits in the maximum value (e.g. d=3 for numbers up to 999). For a fixed range of integers, d is a constant, making this effectively O(n).

Radix Sort vs Comparison-Based Sorts

When to Use Radix Sort

• Sorting large arrays of integers or fixed-length strings where d is small
• When you need a stable sort with better than O(n log n) performance
• Sorting IP addresses, phone numbers, dates, or fixed-length codes
• Not suitable for: floating-point numbers, variable-length strings, or when extra O(n) memory is not available

Related Sorting Programs in C

• Quick Sort in C — O(n log n) average, best general-purpose sort
• Merge Sort in C — stable O(n log n)
• Heap Sort in C — O(n log n) guaranteed, O(1) space
• Bubble Sort in C
• Selection Sort in C

As an Amazon Associate we earn from qualifying purchases.

Further Reading

The definitive reference for C — The C Programming Language by Brian Kernighan and Dennis Ritchie. Covers every concept on this site: pointers, arrays, structs, file I/O, and the standard library. Worth having on your desk.