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.