Counting sort is a sorting technique based on keys between a specific range. It works by counting the number of objects having distinct key values (a kind of hashing). Then do some arithmetic operations to calculate the position of each object in the output sequence.
lets assume we have an array where the biggest number in this array is less than or equal to n:
# in this example n is 9.
a[] = {1,2,2,2,2,3,3,5,7,2,8,4,6,7,4,9};
we start by counting the occurences of each number and store them in a secondary array:
for i in a:
b[i] += 1
then we store the last position of the number i in the sorted array a in a different array called c or we can also overwrite b because we don’t need it anymore:
for i in range(1,n):
b[i] +=b[i-1]