Counting Sort

Counting occurrences can replace comparing pairs

Comparison sorting decides order by asking which pair of elements is smaller. Counting sort uses a different fact about this array: every value is a nonnegative integer, so you can give each possible value its own slot. For values from 0 through 8, the frequency array has nine slots, and slot v stores how many times value v appears.

int values[] = {4, 2, 2, 8, 3, 3, 0};
int frequency[9] = {0};

for (int value : values) {
    frequency[value]++;
}

Start with nine zeroes for slots 0 through 8. The first 4 increments slot 4. The two 2 values both increment slot 2, so that slot reaches 2. The two 3 values likewise make slot 3 equal to 2. The 8 increments slot 8, and the final 0 increments slot 0. The completed frequency array is [1, 0, 2, 2, 1, 0, 0, 0, 1].

Reading value slots from left to right produces sorted order

Once the frequencies are known, scan the value slots from 0 through 8. For each slot, append its value exactly as many times as its frequency says. A zero-frequency slot writes nothing, so slot 1 and slots 5 through 7 leave the output unchanged. Because smaller slot indices are processed first, every value is appended after values no larger than it.

int outputIndex = 0;

for (int value = 0; value <= 8; value++) {
    for (int count = 0; count < frequency[value]; count++) {
        values[outputIndex] = value;
        outputIndex++;
    }
}

The scan writes one 0 from slot 0, nothing from slot 1, two 2s from slot 2, two 3s from slot 3, one 4 from slot 4, nothing from slots 5 through 7, and one 8 from slot 8. The output becomes [0, 2, 2, 3, 3, 4, 8]. The seven written values match the seven input values, including every duplicate.

The key range controls the cost even when n stays small

Counting the seven input values takes O(n) time because the counting pass visits each input once. Reconstruction takes O(n + k) time: the inner writes produce n output values, while the outer scan visits all k value slots. Here n = 7 and k = 9, because the frequency array covers slots 0 through 8.

The frequency array uses O(k) extra space, which is nine slots in this run. The value 8 is the maximum, so every slot from 0 through 8 must exist even though several are empty. If the same seven inputs included a very large maximum instead, k would become very large, forcing counting sort to store and scan many slots that contain zero. Not comparing elements does not make the cost O(n) for every possible range.

Two conserved facts prove that reconstruction is correct

The first fact is that the frequencies always sum to n after counting. Here 1 + 0 + 2 + 2 + 1 + 0 + 0 + 0 + 1 equals 7, the number of input values. Reconstruction writes exactly one output value for every counted occurrence, so it cannot lose an element or invent an extra one.

The second fact is about order. When the scan reaches a value slot, every earlier slot has a smaller value, and the current slot writes only copies of its own value. Therefore each newly written value is at least as large as every value already written. The completed output [0, 2, 2, 3, 3, 4, 8] is sorted because increasing slot order preserves that rule.