Counting Sort is a non-comparison sort that counts how many times each distinct value appears, then uses those counts to place elements in sorted order. It runs in O(n + k) where k is the value range. It is extremely fast when k is small relative to n, and is used as a subroutine in Radix Sort.
void countingSort(vector<int>& arr) {
int maxVal = *max_element(arr.begin(), arr.end());
vector<int> count(maxVal+1, 0), output(arr.size());
for (int x : arr) count[x]++;
for (int i = 1; i <= maxVal; i++) count[i] += count[i-1];
for (int i = arr.size()-1; i >= 0; i--) output[--count[arr[i]]] = arr[i];
arr = output;
}Counting Sort breaks the O(n log n) comparison sort lower bound by not comparing elements. Instead it exploits the fact that integer values can be used as array indices directly.
We count occurrences of each value, then compute prefix sums to determine the final position of each value. Prefix sums tell us: how many elements are less than or equal to value v.
By iterating the input array backwards when placing elements, Counting Sort is stable: equal elements appear in the same relative order in the output as in the input.
Counting Sort requires O(k) extra space for the count array. It is impractical when k (the value range) is much larger than n. Negative numbers require an offset transformation.
Quiz coming soon for this algorithm.