Counting Sort runs in \(O(n+k)\) time and \(O(k)\) space in all cases, where \(n\) is the number of elements and \(k\) is the range of possible values; it’s efficient when \(k\) is not much larger than \(n\). It avoids comparisons by directly counting occurrences of each integer and reconstructing the sorted array.

Here is the idea:

1. Create an array histo of size c, initialised to all 0.
2. For every element x in the array, increment histo by 1.
3. Iterate on v from 0 to c-1: Output v as many times specified by histo[v]

Stable sorting is possible if implemented carefully.

To make counting sort stable we use the following ideas:

1. We store the range of indices where each key will fall in the sorted array
2. We can traverse from the back of the initial array and put the elements in the ranges stored

Now the question is how to get the range of indices. This is easy: just calculate the prefix-sum of the histo array. This tells us to max index an element with that key could occupy.

Limitation: Not suitable when \(k \gg n\).

function counting_sort(array A):
    let n = length(A)
    let k = maximum value in A

    create count[0..k] initialized to 0

    for each element x in A:
        count[x] += 1

    create output array B of size n
    index = 0
    for value from 0 to k:
        while count[value] > 0:
            B[index] = value
            index += 1
            count[value] -= 1

    return B

Explanation:

• Count how many times each integer occurs.
• Walk through the count array and emit each integer the number of times it appeared.
• Result is sorted without comparisons.

Example Problems

Counting Sort is particularly useful in problems where:

• Input values are bounded integers (e.g., scores, frequencies, colors).
• Range (k) is small relative to (n).
• Sorting must be fast and stable.

Here are some examples:

1. HackerEarth – Shil and Birthday Present

   Problem involves distributing gifts with bounded integer values; Counting Sort is the optimal way to sort and count efficiently.

2. Finding Pairs

   Requires sorting bounded integers to quickly find valid pairs; Counting Sort avoids the overhead of comparison-based sorting.