In this tutorial, we’ll learn about counting sort algorithm in Python.

Counting sort is a stable sorting algorithm, which uses the frequencies of each element in the array to sort the given array in linear time. However, it is efficient only when the range of the input data is not much greater than the number of elements in the input array.

## Counting Sort Algorithm

This algorithm sorts a list of objects by mapping the number of occurrences of each distinct object to the object’s value (using a count array).

Say, we’re given an array of integers size ‘n’ whose maximum element is ‘max’.

- Construct a
`count`

array of size max+1, where,`count[i]`

is the number of times`i`

occurs in the input array`arr`

. - Update the count array, so that each element in the array stores the cumulative count at that index. i.e.,
`count[i] = ∑count[k]`

where`0<=k<=i`

. - Now, for an integer
`i`

,`count[i]`

is the number of elements less than or equal to`i`

in the array arr. So, what does this number say? It represents the last position that, that item can occur in the output array. i.e., for a given`i`

,`count[i]`

is the last position where`i`

can occur in`res`

. - Iterate through the input array
`arr`

, for each element`arr[i]`

, fill the output array as`output[count[arr[i]]-1]=arr[i]`

and decrement`count[arr[i]]`

by one. - The resulting
`output`

array is the sorted sequence.

## Python Solution

```
def countingSort(arr):
count = [0]*(max(arr)+1)
res = [0]*len(arr)
for num in arr:
count[num] = count[num]+1
for i in range(1,len(count)):
count[i] = count[i-1]+count[i]
for num in arr:
res[count[num]-1] = num
count[num] = count[num]-1
print("The sorted array is ", res)
return
if __name__ == "__main__":
arr = [5,2,4,2,1,5,1,5]
countingSort(arr)
```

Output:

```
The sorted array is [1, 1, 2, 2, 4, 5, 5, 5]
```

## Java Solution

```
import java.util.*;
import java.io.*;
public class countingSort
{
public static void main(String[] args)
{
int arr[] = {5,2,4,2,1,5,1,5};
int n = arr.length, max;
int res[] = new int[n];
//finding maximum element in the array
max = arr[0];
for(int i=0;i<n;i++)
max = (arr[i]>max) ? (arr[i]) : (max);
//count array and cumulative count
int count[] = new int[max+1];
for(int i=0;i<n;i++)
count[arr[i]]++;
for(int i=1;i<count.length;i++)
count[i] = count[i]+count[i-1];
//filling the result array
for(int i=0;i<n;i++)
{
res[count[arr[i]]-1] = arr[i];
count[arr[i]]--;
}
//printing the result
for(int i=0;i<n;i++)
System.out.print(res[i]+" ");
}
}
```

### Output

`1 1 2 2 4 5 5 5`

## Complexity Analysis

**Time complexity :** `O(n+max)`

(`O(n)`

for iterating through the input, result array and `O(max)`

for iterating through the count array)

**Space complexity :** `O(max)`

Therefore, larger the range of elements, larger is the space complexity.

It can be seen that counting sort runs in almost linear time unlike the comparison-based sorting algorithms like the bubble sort, quick sort etc and proves to be the most efficient choice to sort a set of objects when the range of the input data is not much greater than the number of items to be sorted.

The above algorithm can be further extended to sort an array with negative numbers by mapping the least negative number to the 0th index in the count array.

## Taking it further

So, we’ve learnt that counting sort can sort an array efficiently in linear time, unlike the comparison-based sorting algorithms which can give a best-case time complexity of `O(n logn)`

. So, what if, you’re given an array, whose length is n, and it’s elements range from 1 to n^{2 }?? Will it be a wise choice to go for counting sort now??

NO! In such a case, counting sort performs with time complexity of `O(n`

^{2}`)`

(worse than comparison based sorting algo).. So, is there no way to sort such an array in linear time?

In such a case, radix sort comes to the rescue. It is interesting to note that, Radix sort, in turn, uses counting sort as a subroutine to sort.

## References:

Happy Learning 🙂