A few years ago, I was working with a colleague who was building a high-frequency trading telemetry tool. He was tasked with sorting millions of 32-bit sequence IDs every few seconds to detect gaps in the data stream. He started with qsort(), which is the standard C approach, but as the data volume grew, he hit a wall. The $O(n \log n)$ complexity of comparison-based sorting was eating up too much of his CPU budget. He came to me frustrated, complaining that the hardware couldn't keep up. I told him he was thinking about sorting the wrong way. He was treating the IDs as opaque values to be compared, rather than as strings of digits. That's when we swapped in Radix Sort, and the performance jump was immediate.

Breaking the Comparison Barrier

Most of the sorting algorithms you've encountered so far—like QuickSort or MergeSort—are "comparison sorts." They ask, "Is A greater than B?" and move things around based on the answer. Because of the mathematical limits of decision trees, these will always be bound by $O(n \log n)$. Radix Sort is different. It's a non-comparison sort. Instead of comparing two numbers, it exploits the internal representation of the keys. It groups numbers by their individual digits.

We typically implement this as a Least Significant Digit (LSD) sort. We sort the list based on the ones place, then the tens place, then the hundreds, and so on. The "magic" that makes this work is stability. If two numbers have the same digit in the current place being sorted, their relative order from the previous (less significant) pass must be preserved. In C, this means we can't just use any sorting method for the individual digits; we need a stable subroutine, and Counting Sort is the industry standard for this.

The Counting Sort Engine

To build a Radix Sort, you first need a version of Counting Sort that can target a specific digit. In C, we isolate a digit using a combination of division and the modulo operator: (array[i] / exp) % 10. Here, exp is our current place value (1, 10, 100, etc.).

void countingSortForRadix(int arr[], int n, int exp) {
    int output[n]; 
    int count[10] = {0};

    // Store count of occurrences in count[]
    for (int i = 0; i < n; i++) {
        count[(arr[i] / exp) % 10]++;
    }

    // Change count[i] so that count[i] now contains actual
    // position of this digit in output[]
    for (int i = 1; i < 10; i++) {
        count[i] += count[i - 1];
    }

    // Build the output array (Looping backwards ensures 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 output array to arr[], so that arr[] now
    // contains sorted numbers according to current digit
    for (int i = 0; i < n; i++) {
        arr[i] = output[i];
    }
}

Notice the loop that builds the output array runs backwards. I cannot stress this enough: if you loop forwards here, you lose stability, and your Radix Sort will fail miserably. Stability is what ensures that when we move from the ones place to the tens place, we don't scramble the work we already did.

Orchestrating the Full Sort

Now that we have the engine, the main Radix function is surprisingly simple. We find the maximum number in the array to determine how many digits we need to process, and then we call our counting sort in a loop, multiplying our exponent by 10 each time.

void radixSort(int arr[], int n) {
    // Find the maximum number to know number of digits
    int max = arr[0];
    for (int i = 1; i < n; i++) {
        if (arr[i] > max) max = arr[i];
    }

    // Do counting sort for every digit. 
    // exp is 10^i where i is current digit number
    for (int exp = 1; max / exp > 0; exp *= 10) {
        countingSortForRadix(arr, n, exp);
    }
}

The time complexity here is $O(d \cdot (n + k))$, where $d$ is the number of digits and $k$ is the range of the digits (which is 10 for decimal). Since $d$ is often a small constant for a given data type (e.g., a 32-bit integer has a maximum of 10 decimal digits), this effectively performs in linear time $O(n)$. It's incredibly fast, provided you have the extra memory for the output and count arrays.

📋 Practical Task

Exercise: Sorting a Million 32-bit Network Sequence IDs

You are simulating a network packet analyzer. You have an array of 1,000,000 unsorted 32-bit integers representing sequence IDs. Your goal is to implement the Radix Sort logic discussed in this lesson to sort these IDs as efficiently as possible.

• Create a program that generates an array of 1,000,000 random integers (use rand()).
• Implement the countingSortForRadix and radixSort functions.
• Use the clock() function from time.h to measure the execution time of your Radix Sort.
• Challenge: For comparison, implement a call to the standard library qsort() on a second identical copy of the array and print both execution times. You should see a significant performance advantage with Radix Sort for this specific data size.