Radix Sort is a non-comparative integer sorting algorithm. Unlike Merge Sort or Quick Sort, which sort by comparing two elements at a time, Radix Sort works by processing the individual digits of the numbers. It sorts numbers digit by digit, usually starting from the least significant digit (LSD) to the most significant digit (MSD).

Think of how you might organize a large stack of dates (DD/MM/YYYY). You wouldn't compare every date to every other date. Instead, you might first sort them into piles by Day (1-31). Then, you gather them up and sort them by Month (1-12), preserving the order of days. Finally, you sort by Year. By the end, the entire stack is sorted chronologically. This is exactly how Radix Sort works!

Radix Sort uses a stable sorting algorithm (usually Counting Sort) as a subroutine to sort by each digit place.

• Find Max: Determine the maximum number to know the number of digits d we need to process.
• Iterate Digits: Start with the least significant digit (1s place). Sort the entire array based ONLY on this digit using a stable sort.
• Move Left: Move to the next significant digit (10s place) and sort again, preserving the relative order of items with the same 10s digit.
• Repeat: Continue this process until the most significant digit is processed.

Let's trace the algorithm on a small array using LSD (Least Significant Digit) Radix Sort.

Below is the implementation of Radix Sort in multiple programming languages.

#include <stdio.h>
#include <stdlib.h>
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;
}
void countSort(int arr[], int n, int exp) {
    int* output = (int*)malloc(n * sizeof(int));
    int count[10] = {0};
    
    // Count occurrences based on digit
    for (int i = 0; i < n; i++)
        count[(arr[i] / exp) % 10]++;
    
    // Compute cumulative count
    for (int i = 1; i < 10; i++)
        count[i] += count[i - 1];
    
    // Build output array
    for (int i = n - 1; i >= 0; i--) {
        output[count[(arr[i] / exp) % 10] - 1] = arr[i];
        count[(arr[i] / exp) % 10]--;
    }
    
    for (int i = 0; i < n; i++)
        arr[i] = output[i];
    
    free(output);
}
void radixSort(int arr[], int n) {
    int max = getMax(arr, n);
    
    // Apply counting sort for each digit
    for (int exp = 1; max / exp > 0; exp *= 10)
        countSort(arr, n, exp);
}
int main() {
    int arr[] = {170, 45, 75, 90, 802, 24, 2, 66};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    radixSort(arr, n);
    
    printf("Sorted array: ");
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    return 0;
}

Radix Sort can be faster than comparison sorts for large lists of integers, but it depends heavily on the number of digits.

Time Complexity

Space Complexity

Radix Sort is specialized for specific data types and constraints.