# Counting Sort

When the range of possible values of the elements of a sequence is small and known ahead of time, counting sort may be employed, enabling sorting in linear time `O(n)`

, with respect to the number of elements `n`

of the sequence.

Counting sort consists of counting the number of occurrences of each possible value, then placing each occurrence in order in a new sequence, which will be sorted by construction.

## Naive implementation

Good enough for when there is no satellite data associated with the elements.

def counting_sort(arr, upper_bound): f = [0 for i in range(upper_bound+1)] for e in arr: f[e] += 1 r = [] for i in range(upper_bound+1): for j in range(f[i]): r.push(i) return r

## Stable implementation

The order of the elements in the original array is preserved. (TODO)