Counting Sort

Counting sort is a non-comparison sorting algorithm which means we don’t have to compare the elements with each other for sorting instead we will sort by counting the number of elements having distinct key values. Then we perform some arithmetic on those counts to calculate the appropriate position of the elements in the output array or final sequence.

WORKING

First, we will find the maximum element(k) in the given array. Then we will make another array(count) of length max+1 to store the count of every element having distinct key values. At first, we will initialize the count array with all the elements zero and then we will store the count of each distinct element using for loop. Now we will update our count array so that we can place the elements in their actual position in the sorted array.
We will update the count array by storing the cumulative sum of the elements of the count array. Then we will make another array(a) having the same length as the original array(arr). Now we will start iterating in the array arr from the last element(to maintain the stability of the algorithm) and start positioning the elements in their appropriate position in array ‘a’ using count array. Then finally we will copy the output array into the original array.

PICTORIAL REPRESENTATION WITH EXAMPLE

1. We have given an array(arr) to sort, first we will find the maximum element(k=8(here)) in the given array arr. Then to store the count of the distinct elements present in arr we will make an array(count) of length k+1(9) and initialize all the elements 0, as you can see in the figure given below.

2. Then we will count the distinct elements and store the frequency in the count array using for loop. 1 is present 2 times in the given array arr, so 2 is stored at index 1 of the count array and 6 is not present in the arr so 0 is stored at index 6 of the count array.

3. Now we will update the count array by storing the cumulative sum of the elements. For this, we will add the current element with the previous element, as you can see in the figure,
value at index 1= value at index 0+value at index 1(before the update)[0+2=2]
value at index 2= value at index 1+value at index 2(before the update)[2+3=5]And the same for the rest of the elements.

4. We will make another array(a) having the same length as the original array, in this, we will store the elements in a sorted manner. We will start iterating in the arr from the last index, the element at the last index is 1, then we will go to index 1 on the count array, then we will decrease the value at index 1 of count array by 1(2–1=1), then we will go to index 1 of the array a and store the element(1) on which i(here i=9) is pointing in the array arr.

PSEUDOCODE

for(int i=0;i<n;i++)
{
// Finding the maximum element in arr
if(arr[i]>k)
k=arr[i];
}
int l=k+1;
int count[l];
for(int i=0;i<l;i++)
{
//initialising all the elements 0
count[i]=0;
}
for(int i=0;i<n;i++)
{
//storing the count of every distinct element
count[arr[i]]++;
}
for(int i=1;i<l;i++)
{
//updating the count array by adding current element and it’s previous
element(cumulative sum)
count[i]=count[i]+count[i-1];
}
int a[n];
for(int i=n-1;i>=0;i — )
{
//positioning the elements in their appropriate positions in output array
a[ — count[arr[i]]]=arr[i];
}
for(int i=0;i<n;i++)
{
//copying
arr[i]=a[i];
}

COMPLEXITY

Mainly there are only five for loops in our algorithm that will affect our time complexity. The first loop is for finding the maximum element in the given array which is executed n times, the second loop is for initializing the count array which is executed l times, the third loop is for storing the frequency of distinct elements which is also executed n times, the fourth loop is for updating the count array which is executed l times and the last loop for arranging the elements in the sorted manner which is executed for n times. After adding the time of each loop, the time complexity of the whole algorithm is O(n+l).
As counting sort is a non-comparison sorting algorithm so time complexity does not depend on the order of the elements in the array, therefore in all the cases(worst, best, average) time complexity will remain same i.e. O(n+l).
As only arrays of sizes n and l are used in the algorithm so space complexity is O(n+l).

Where to use?

We can only use this algorithm when the difference between the range of the elements and the number of objects is not much. For example, if the given array is {10 , 5 , 10k , 100}. So the length of the count array will be max+1 i.e. 10001, the array of this size will contain only 4 elements which result in wastage of lots of space, hence it is not feasible or efficient to use counting sort for sorting those type of arrays where the range of the element is much greater than the size of the array.

The proposed algorithm is only applicable for the arrays having positive elements, you can modify it for negative elements by performing normalization or you can use any other method.