Counting sort

Counting sort works when keys are integers in a known, small range [min, max] of size k = max - min + 1. It stores one counter per possible key, so it needs O(k) extra memory.

That is only a good deal when k is not much larger than n. Sorting 10 numbers between 1 and 1,000,000,000 would need a billion counters. Try the “Big gap (wasteful)” preset: five values need 19 counters.

Pass 1 counts frequencies: count[x - min]++ for each element. Pass 2 turns the frequencies into prefix sums, count[v] += count[v - 1]. After that, count[v] is the number of elements with key <= v, which is also the index one past where the last copy of key v belongs in the output.

Pass 3 places elements. Walk the input right to left, decrement count[key], and write the element at that index. Watch the count row change from frequencies to prefix sums and then shrink while the output row fills.

1public static int[] countingSort(int[] arr) {
2    int min = min(arr), max = max(arr);
3    int[] count = new int[max - min + 1];
4    for (int x : arr) count[x - min]++;
5    for (int v = 1; v < count.length; v++) count[v] += count[v - 1];
6    int[] out = new int[arr.length];
7    for (int i = arr.length - 1; i >= 0; i--) {
8        out[--count[arr[i] - min]] = arr[i];
9    }
10    return out;
11}

Walking the input from right to left while decrementing the counter places the last of several equal keys in the last slot of its block, the next-to-last in the slot before it, and so on. Equal keys therefore stay in their original order.

Stability is what makes counting sort usable as the digit pass of radix sort in the next lesson. Walking left to right would still sort the keys correctly but would reverse the order of equal keys. Run the “Stability check” preset and read the a/b tags.

1public static int[] countingSort(int[] arr) {
2    int min = Arrays.stream(arr).min().getAsInt();
3    int max = Arrays.stream(arr).max().getAsInt();
4    int[] count = new int[max - min + 1];
5    for (int x : arr) count[x - min]++;
6    for (int v = 1; v < count.length; v++) count[v] += count[v - 1];
7    int[] out = new int[arr.length];
8    for (int i = arr.length - 1; i >= 0; i--) {   // right to left keeps it stable
9        out[--count[arr[i] - min]] = arr[i];
10    }
11    return out;
12}

Array indices cannot be negative, so subtract the minimum key: x - min. The smallest key maps to index 0 and the largest to max - min. Add min back when you need the key value from a counter index.

The “Negative keys” preset sorts values between -4 and 5 with ten counters. If you accidentally use x as the index, a key of -2 throws ArrayIndexOutOfBoundsException.

Time: one pass over the input to count (n), one over the counters for the prefix sums (k), one over the input to place (n): O(n + k). Space: the counter array plus the output array, O(n + k).

When k = O(n) this is linear, beating the Ω(n log n) lower bound for comparison sorts. There is no contradiction: counting sort never compares two elements, so the bound does not apply to it.