Radix sort

Sort integers digit by digit, from the ones place up, using a stable counting sort as the subroutine for each digit.

The idea

Instead of comparing whole numbers, radix sort looks at one digit position at a time, starting from the least significant digit. Each pass uses a stable counting sort to group the array by that digit value, and because the sort is stable, the ordering set up by earlier, less significant digit passes stays intact within each group. After every digit position has had a pass, the whole array is sorted.

Code

public static void RadixSort(int[] a) {
    int max = a.Max();
    for (int exp = 1; max / exp > 0; exp *= 10)
        CountingSortByDigit(a, exp);
}

static void CountingSortByDigit(int[] a, int exp) {
    int n = a.Length;
    var output = new int[n];
    var count = new int[10];
    foreach (int x in a) count[(x / exp) % 10]++;
    for (int d = 1; d < 10; d++) count[d] += count[d - 1];
    for (int i = n - 1; i >= 0; i--) {
        int digit = (a[i] / exp) % 10;
        output[--count[digit]] = a[i];
    }
    Array.Copy(output, a, n);
}

Tips

• Process digits from least significant to most significant, and use a stable sort for each digit, or earlier passes get undone.
• Works directly on fixed-width keys such as integers; needs adapting for arbitrary objects or variable-length strings.

In the .NET library

LINQ OrderBy cannot do this trick because it only compares two items at a time; radix sort needs a way to read digits or bytes directly out of the key, which plain comparison does not give you.