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 occurences of each possible value, then placing each occurence in order in a new sequence, which will be sorted by construction.
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
The order of the elements in the original array is preserved. (TODO)