Counting Sort Works by Counting a Controlled Range

Counting sort replaces comparisons with occurrence counts

Take the input array [4, 2, 2, 8, 3, 3, 1]. A comparison sort would compare elements and move them into order. Counting sort does neither. It creates one count slot for every value from the minimum value 1 through the maximum value 8, then records how often each value occurs.

The range width is k = 8 because the values 1 through 8 need eight slots. An input value becomes a count-array index by subtracting the minimum value: count[value - 1]. For example, value 4 updates count[3], while value 1 updates count[0]. The subtraction is an offset that makes the minimum value use index 0.

int minValue = 1;
int maxValue = 8;
int k = maxValue - minValue + 1;
vector<int> count(k, 0);

for (int value : a) {
    count[value - minValue]++;
}

Each count index belongs to exactly one value

For this array, count starts as [0, 0, 0, 0, 0, 0, 0, 0]. Each input value increments exactly one slot. The first 4 increments index 3, the first 2 increments index 1, the second 2 increments that same index, and the rest follow the same rule. Duplicate values do not need separate slots.

The final count array is [1, 2, 2, 1, 0, 0, 0, 1]. Its index-to-value mapping is exact: count index j stores the frequency of value 1 + j. Therefore index 0 describes value 1, index 1 describes value 2, index 2 describes value 3, and index 7 describes value 8.

Repeating each value by its count reconstructs the sorted array

Once the count array is complete, scan it from index 0 to index 7. For each index j, the represented value is 1 + j. Write that value as many times as the count at index j. A count of 0 emits nothing, a count of 1 emits one value, and a count of 2 emits the associated value twice.

int write = 0;
for (int j = 0; j < k; j++) {
    for (int repeats = 0; repeats < count[j]; repeats++) {
        a[write++] = minValue + j;
    }
}

For [1, 2, 2, 1, 0, 0, 0, 1], index 0 writes 1 once, index 1 writes 2 twice, and index 2 writes 3 twice. Indices 4, 5, and 6 write nothing because their counts are zero. Index 7 writes 8 once. The input is overwritten as [1, 2, 2, 3, 3, 4, 8], without swapping any pair of elements.

a[write++] = ____________________

O(n + k) is efficient only when the value range is controlled

Building the count array makes one pass over the n = 7 input values. Reconstruction makes one pass over the k = 8 count slots, plus the writes for the seven values that occur. The total time is O(n + k), and the count array uses O(k) extra space. For this example, n and k are both small, so the method is practical.

The bound is not automatically O(n) just because the input is scanned once. If the minimum stayed 1 while the maximum became extremely large, k would also become extremely large. The count array would still allocate and scan every slot between 1 and that maximum, including slots for values that never occur. Counting sort is therefore useful when the value range is controlled, not merely when the input has n elements.