Radix sort definition and algorithm

Radix sort is a non-comparison sorting method that sorts keys digit by digit, starting from the least significant digit (LSD) and moving to the most significant digit. For each digit position the keys are distributed into 10 queues (pockets), numbered 0 to 9, and then collected back in queue order. Because each pass is stable, after the last pass the list is sorted.

Algorithm

1. Find the largest key and count its digits, d.
2. For pass = 1 to d (units, tens, hundreds, ...):
   1. Take each key from the list in order and insert it at the rear of queue[digit], where digit is the current digit of the key.
   2. Delete all keys from queue 0, then queue 1, ... up to queue 9 (front to rear) and place them back in the list.
3. After d passes the list is sorted.

void radixSort(int a[], int n) {
    int max = a[0], exp, i, j, k;
    for (i = 1; i < n; i++) if (a[i] > max) max = a[i];
    for (exp = 1; max / exp > 0; exp *= 10) {
        int q[10][100], cnt[10] = {0};          /* 10 queues */
        for (i = 0; i < n; i++) {               /* distribute */
            int d = (a[i] / exp) % 10;
            q[d][cnt[d]++] = a[i];
        }
        k = 0;
        for (j = 0; j < 10; j++)                /* collect */
            for (i = 0; i < cnt[j]; i++) a[k++] = q[j][i];
    }
}

Complexity: each pass takes O(n) and there are d passes, so time is O(d·n) (O(n) when d is fixed). Extra space is O(n) for the queues. It is stable and needs no key comparisons.