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[1]=3, v=2. After adding 1 to B[2], count[1]=2 and i=1

Figure 4: For i=0

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

Figure 5: For i=1

• For i=2, t=2, count[2]= 5, v=4. After adding 2 to B[4], count[2]=4 and i=3

Figure 6: For i=2

• For i=3, t=8, count[8]= 10, v=9. After adding 8 to B[9], count[8]=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.