Counting sort and radix sort

Every sort so far works by comparing two items. It can be proved that any comparison-based sort needs about n log n comparisons in the worst case. There are n! possible orders of n items, and each yes/no comparison can at best halve the remaining possibilities, so you need log₂(n!) ≈ n log₂ n comparisons to identify the right one.

To go faster you must stop comparing and use the values themselves. That only works when the keys are small whole numbers (or can be split into them), but when they are, the speed-up is real.

Counting sort

If every value is between 0 and k − 1, make an array of k counters. One pass counts how often each value appears. A running total turns counts into positions (“values ≤ 3 fill the first 7 slots”). A final pass places each item directly into its slot.

1static int[] CountingSort(int[] a)2{3    if (a.Length == 0) return a;4    int min = a.Min(), max = a.Max();5    var count = new int[max - min + 1];          // k = range of values6 7    foreach (int v in a) count[v - min]++;       // 1. count8 9    for (int i = 1; i < count.Length; i++)       // 2. running totals = end positions10        count[i] += count[i - 1];11 12    var output = new int[a.Length];13    for (int i = a.Length - 1; i >= 0; i--)      // 3. place, right to left = stable14        output[--count[a[i] - min]] = a[i];15    return output;16}17 18Console.WriteLine(string.Join(" ", CountingSort([4, 1, 3, 4, 0, 2, 1, 4, 3, 1])));19Console.WriteLine(string.Join(" ", CountingSort([3, -2, 0, 3, 1])));

0 1 1 1 2 3 3 4 4 4
-2 0 1 3 3

Time O(n + k), extra space O(n + k). When k is small compared with n (exam marks 0 to 100, floor numbers, ages, status codes) this beats any comparison sort. When k is huge (values up to a billion), the counter array becomes the problem.

Radix sort

Radix sort handles large numbers by sorting on one digit at a time, starting with the least significant digit (LSD). Each pass is a stable counting sort with only 10 possible keys (0 to 9). After the ones pass, the tens pass, and the hundreds pass, the numbers are fully sorted, because the stable passes keep the earlier digit order inside each group.

1// LSD radix sort for non-negative integers, base 102static void RadixSort(int[] a)3{4    if (a.Length == 0) return;5    int max = a.Max();6    var output = new int[a.Length];7 8    for (int exp = 1; max / exp > 0; exp *= 10)          // 1, 10, 100, ...9    {10        var count = new int[10];11        foreach (int v in a) count[v / exp % 10]++;12        for (int d = 1; d < 10; d++) count[d] += count[d - 1];13        for (int i = a.Length - 1; i >= 0; i--)          // stable14            output[--count[a[i] / exp % 10]] = a[i];15        Array.Copy(output, a, a.Length);16    }17}18 19int[] data = { 170, 45, 75, 90, 802, 24, 2, 66 };20RadixSort(data);21Console.WriteLine(string.Join(" ", data));

2 24 45 66 75 90 170 802

With d digits and base b, radix sort is O(d × (n + b)). For 32-bit integers, real implementations use base 256 (one byte per pass): just 4 passes over the data, whatever n is.

1using System.Text;2 3static string SortLetters(string s)4{5    var count = new int[26];6    foreach (char c in s) count[c - 'a']++;7 8    var sb = new StringBuilder(s.Length);9    for (int i = 0; i < 26; i++)10        sb.Append((char)('a' + i), count[i]);11    return sb.ToString();12}13 14Console.WriteLine(SortLetters("algorithms"));

aghilmorst