Counting Sort

This can sort an array in $O(n)$ time assuming that every element in the array is an integer between $0\dots c$ and $c=O(n)$

The idea is to store the frequency of each value in the array. So you can do it in 2 sweeps of $0(n)$

1. First sweep is to get the max value of the array. Then, create an array
2. Second sweep is to store the frequencies of theses arrays.

Counting sort is a very efficient algorithm but it can only be used when the constant $c$ is small enough. The array elements can be used as indices in the bookkeeping array.

Q

Same thing as Bucket Sort? Radix and bucket sorts thus are two useful generalizations of counting sort. Stackoverflow.