Counting sort is not a comparison sort algorithm and gives O(n) complexity for sorting. To achieve O(n) complexity, counting sort assumes that each of the elements is an integer in the range of 1 to K, for some integer K. When K = O(n), the counting sort works in O(n) time. The basic idea of counting sort is to determine, for each input elements X, the number of elements less than X. This information can be used to place directly into its correct position. For example, if there are 10 elements less than X, then X belongs to position 11 in the output.

In the below example, **arr[0..n – 1]** is the input array with length n. In counting sort we need two more arrays: let us assume array **temp[0..n – 1]** as another array and **out[0..n – 1]** as the final sorted array.

Here is an implementation of the algorithm:-

void countingSort(int arr[], int size, int out[], int k) { //arr[] - is the original array. //size - the size of array //out[] - the final sorted array //K - the maximum value in array int temp[k], i ,j; // thus space complexity = O(K) for(i = 0;i < k;i++) temp[i] = 0; // initialize all to ZERO //now we traverse through the original array //and increment the count at the location. //Eg: if we get an element "56", then we do temp[56]++ for(j = 0;j < size;j++) temp[arr[j]] = temp[arr[j]] + 1; // temp[i] now contains the number of elements equal to i for(i = 1;i < K;i++) temp[i] = temp[i] + temp[i-1]; // temp[i] now contains the number of elements <= i //time to make the final sorted array for(j = size;j >= 0;j--) { //filling the array out[temp[arr[j]]] = arr[j]; //decrement the count for each added element. temp[arr[j]] = temp[arr[j]] - 1; } }