Counting Sort Algorithm is an efficient sorting algorithm that can be used for sorting elements within a specific range. This sorting technique is based on the frequency/count of each element to be sorted and works using the following algorithm-

• Input: Unsorted array A[] of n elements
• Output: Sorted arrayB[]

Step 1: Consider an input array A having n elements in the range of 0 to k, where n and k are positive integer numbers. These n elements have to be sorted in ascending order using the counting sort technique. Also note that A[] can have distinct or duplicate elements

Step 2: The count/frequency of each distinct element in A is computed and stored in another array, say count, of size k+1. Let u be an element in A such that its frequency is stored at count[u].

Step 3: Update the count array so that element at each index, say i, is equal to - Step 4: The updated count array gives the index of each element of array A in the sorted sequence. Assume that the sorted sequence is stored in an output array, say B, of size n.

Step 5: Add each element from input array A to B as follows:

1. Set i=0 and t = A[i]
2. Add t to B[v] such that v = (count[t]-1).
3. Decrement count[t] by 1
4. Increment i by 1

Repeat steps (a) to (d) till i = n-1

Step 6: Display B since this is the sorted array

##### Example of Counting Sort

Let us trace the above algorithm using an example:

Consider the following input array A to be sorted. All the elements are in range 0 to 9

A[]= {1, 3, 2, 8, 5, 1, 5, 1, 2, 7}

Step 1: Initialize an auxiliary array, say count and store the frequency of every distinct element. Size of count is 10 (k+1, such that range of elements in A is 0 to k) Figure 1: count array

Step 2: Using the formula, updated count array is - Figure 2: Formula for updating count array Figure 3 : Updated count array

Step 3: Add elements of array A to resultant array B using the following steps:

• For, i=0, t=1, count=3, v=2. After adding 1 to B, count=2 and i=1 Figure 4: For i=0

• For i=1, t=3, count=6, v=5. After adding 3 to B, count=5 and i=2 Figure 5: For i=1

• For i=2, t=2, count= 5, v=4. After adding 2 to B, count=4 and i=3 Figure 6: For i=2

• For i=3, t=8, count= 10, v=9. After adding 8 to B, count=9 and i=4 Figure 7: For i=3

•  On similar lines, we have the following: Figure 8: For i=4 Figure 9: For i=5 Figure 10: For i=6 Figure 11: For i=7 Figure 12: For i=8 Figure 13: For i=9

Thus, array B has the sorted list of elements.