**Difficulty:** Medium, **Asked-in:** Microsoft, Amazon

As we have seen in this blog, the lower bound of comparison sorting is O(nlogn). The critical question is: Is there a possibility to improve time complexity of sorting algorithm from O(nlogn) to O(n)? Let's think!

If some additional constraints are given on input, we can think of implementing sorting algorithms in O(n) time. For example:

- If input is almost sorted or there are O(n) number of inversions, insertion sort algorithm can sort input in O(n) time.
- If there are only 0's, 1's, and 2's in the array, we can sort such input in O(n) time. This is a famous Dutch National Flag problem.

Similarly, if n input elements are integers in the range [0, k], we can use counting sort algorithm to sort input in O(n + k) time. In other words, counting sort is one of the popular linear time sorting algorithms that works in O(n) time if input elements are integers in the range 0 to k, where k = O(n).

Instead of comparison operation, counting sort uses array indexes to determine the relative order of elements. For each element x, counting sort counts number of elements less than x and places element x directly into its correct position in the sorted array.

For example, if there are 17 elements less than x, x belongs to output position 18. This idea can be modified slightly to handle the situation if elements are repeated. Idea is simple: When values are repeated, we don’t want to place same elements at the same position in output. Even further, we need to maintain the stable order of elements, i.e. if (A[i] == A[j]) and i < j, then A[i] should appear before A[j] in sorted output.

We use two extra arrays: B[n] to store sorted output and C[k + 1] to store count of every possible unique element in the input. The size of count array C[] is k + 1 because the range of input values is [0, k].

At the start, we initialize all values of C[] to 0's.

```
for (int i = 0; i <= k; i = i + 1)
C[i] = 0
```

Now we traverse input array A[] from start and store count of each element A[i] at index A[i] in C[]. In other words, we inspect each element using a loop. If we find an element with value A[i], we increment there count value at C[A[i]]. By end of this process, C[A[i]] holds the count of elements equal to A[i] for each integer 0 <= A[i] <= k.

```
for (int i = 0; i < n; i = i + 1)
C[A[i]] = C[A[i]] + 1
```

At this point, frequency of each element A[i] is stored at C[A[i]]. Now we need to modify C[] to determine the position of each element in sorted output. For this, we count number of elements less than or equal to each element A[i]. How do we do this? Let's think!

Number of elements less than or equal to element with value i = C[0] + C[1] + ... + C[i - 2] + C[i - 1] + C[i] = Number of elements less than or equal to element with value (i - 1) + C[i].

So if we perform running sum on C[] from i = 0 to k, we can store count of elements less than or equal to i for all i in one go. Think!

```
for (int i = 0; i <= k; i = i + 1)
C[i] = C[i - 1] + C[i]
```

At this point, C[] will be in increasing order storing the cumulative sum of all elements less than or equal to A[i] at C[A[i]]. Now we traverse input array to place each element A[i] into its correct position in output array B[]. If all n elements are distinct, C[A[i]] - 1 will be the correct final index of A[i] in output, since there are C[A[i]] elements less than or equal to A[i].

But elements might not be distinct. So we traverse A[] from the right end and decrement C[A[i]] each time after placing A[i] into B[]. Decrementing C[A[i]] causes another element with value A[i] to go to the position immediately before the previous A[i] in output. In other words, this will help us to maintain a stable order for repeated elements. Think!

```
for (int i = n - 1; i < 0; i = i - 1)
{
B[C[A[i]] - 1] = A[i]
C[A[i]] = C[A[i]] - 1
}
```

- By the end of above process, our sorted output will be stored in array B[].

```
void countingSort(int A[], int B[], int k, int n)
{
int C[k + 1]
for (int i = 0; i <= k; i = i + 1)
C[i] = 0
for (int i = 0; i < n; i = i + 1)
C[A[i]] = C[A[i]] + 1
for (int i = 0; i <= k; i = i + 1)
C[i] = C[i - 1] + C[i]
for (int i = n - 1; i < 0; i = i - 1)
{
B[C[A[i]] - 1] = A[i]
C[A[i]] = C[A[i]] - 1
}
}
```

There are four loops in the counting sort algorithm.

- The first loop takes O(k) time.
- The second loop takes O(n) time.
- The third loop takes O(k) time.
- The fourth loop takes O(n) time.

Overall time complexity of counting sort = O(k) + O(n) + O(k) + O(n) = O(k + n). If k = O(n), then counting sort time complexity = O(n)

Space complexity of counting sort = Size of output array B[] + Size of count array C[] = O(n) + O(k) = O(n + k). If k = O(n), then counting sort space complexity = O(n).

- Time and space complexity of counting sort depends on the range of the input data. Counting sort works efficiently if input range k is not significantly greater than number of elements to be sorted. If k = O(n^2), then time and space complexity of counting sort will be O(n^2).
- Counting sort beats O(nlogn) lower bound of comparison sorting because counting sort does not use comparison operation for sorting. Instead, counting sort uses actual values of the elements to identify its correct index in the output.
- Counting sort is a stable sorting algorithm: In output, elements with same value appear in same order as given in the input. It breaks ties between two elements by a simple rule: Whichever element appears first in input appears first in output.
- Stability property is important only when additional data are carried around with elements being sorted. Counting sort stability is important for another reason: It is used as a subroutine in radix sort algorithm.
- Counting sort uses the idea similar to the direct addressing method of hashing to count the occurrence of input elements in O(1).

- How do we extend counting sort algorithm to work for negative inputs also?
- Why are we running the last loop from right end?
- Instead of running the last loop from i = n - 1 to 0, can we modify above implementation by running loop from i = 0 to n - 1? Is the modified algorithm stable?
- How do we modify above algorithm if we want to sort input data given in the range from [a, b]?
- Describe an algorithm for this problem: Given n integers in the range 0 to k, preprocesses its input and then answers any query about how many n integers fall into a given range [a...b] in O(1) time. Your algorithm can use O(n + k) preprocessing time.

Reference: Algorithms by CLRS

**Enjoy learning, Enjoy algorithms!**

Subscribe to get weekly content on data structure and algorithms, machine learning, system design and oops.