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

Of all the sort algorithms the fastest is the Counting sort, whose 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.

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 temp array with 0
 
    for(i=0; i<sizeTemp; i++){
        temp[i] = 0;
    }
 
    for(i=0; i<=e; i++){
        temp[arr[i]-mn]++;
    }
 
    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

Reference: My Blog