Counting Sort

2022-11-27

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)