There are many sorting algorithms like merge sort, quick sort, etc to sort a linear data structure.

Of all the sort algorithms Counting sort is better, because time complexity is approx O(n).

But counting sort is only viable when

• values of element lie in the small range.
• the values are non-negative.

Counting sort make use of an extra array also known as counting array.

Consider the following array [5, 9, 11, 10, 15, 12, 2, 8 ,10] — Min = 2 and Max = 15.

Counting array will store the frequency of each element of the original array at the relative index position. For example in our case, the frequency of 2 will be stored at index 0, frequency of 3 at 1, frequency of 4 at 2 and so on.

Finally, after storing the frequency of each element in the counting array, we will rewrite the original array on the basis of the counting array. For example in our case index position 0 has 1 – it means only a single 2 was present in the original array, index position 1 has 0 – it means no 3 was present in the original array.

Implementation of Counting Sort in C++

#include <stdio.h>
#include <stdlib.h>
 
int main()
{
    int arr[] = {5, 9, 11, 10, 15, 12, 2, 8 ,10};
    countingSort(arr,0,8,2,15);
 
    return 0;
}
 
void countingSort(int arr[], int s, int e, int mn, int mx){
    int i,k=0,sizeTemp = mx-mn+1;
    int temp[sizeTemp]; 

    // Initializing all element of counting array with 0
    for(i=0; i<sizeTemp; i++){
        temp[i] = 0;
    }
 
    //Store the frequency of each element of the original array 
    //at the relative position in counting array
    for(i=0; i<=e; i++){
        temp[arr[i]-mn]++;
    }
 
    //Iterate through the counting array and re-write the original array.
    for (i=mn; i<=mx; i++){
        while(temp[i-mn]-->0){
            arr[k++]=i;
 
        }
    }
 
    for(i=0; i<=8; i++){
        printf("%d ",arr[i]);
    }
 
}

Output

2 5 8 9 10 10 11 12 15

Counting sort should only be used when the input lies in the specific range and space is not an issue.

Reference: My Blog