# Counting Sort

# Counting Sort

Counting sort is a non-comparison sorting algorithm for integer keys within a bounded range. It counts how many times each value appears, then reconstructs the sorted order using these counts.

It runs in linear time when the key range is not significantly larger than the number of elements.

## Problem

Given an array $A$ of $n$ integers where each value lies in a range $[0, k]$, produce a sorted array.

## Idea

Instead of comparing elements, count how many times each value appears.

Let:

* $C[i]$ be the number of elements equal to $i$
* Then expand counts to reconstruct the sorted sequence

For stable sorting, use prefix sums to compute positions.

## Algorithm (basic version)

```id="c1s9xk"
counting_sort(A, k):
    C = array of size k+1 filled with 0

    for x in A:
        C[x] += 1

    i = 0
    for v from 0 to k:
        while C[v] > 0:
            A[i] = v
            i += 1
            C[v] -= 1
```

## Stable Version

To preserve order of equal elements:

1. Count frequencies
2. Compute prefix sums
3. place elements into output array in reverse order

```id="p8d2la"
counting_sort_stable(A, k):
    C = [0] * (k + 1)

    for x in A:
        C[x] += 1

    for i in range(1, k + 1):
        C[i] += C[i - 1]

    B = [0] * len(A)

    for i in range(len(A) - 1, -1, -1):
        x = A[i]
        C[x] -= 1
        B[C[x]] = x

    return B
```

## Example

Let:

$$
A = [4, 2, 2, 8, 3, 3, 1]
$$

Counts:

| value | count |
| ----- | ----- |
| 1     | 1     |
| 2     | 2     |
| 3     | 2     |
| 4     | 1     |
| 8     | 1     |

Reconstructed sorted array:

$$
[1, 2, 2, 3, 3, 4, 8]
$$

## Correctness

Each element contributes exactly one count to its key bucket. The reconstruction step outputs exactly that many copies of each key in increasing order, so the result is sorted.

In the stable version, prefix sums map each occurrence to a unique final index, preserving relative order.

## Complexity

| component      | cost       |
| -------------- | ---------- |
| counting       | $O(n)$     |
| prefix sum     | $O(k)$     |
| reconstruction | $O(n)$     |
| total          | $O(n + k)$ |

Space:

$$
O(n + k)
$$

## Constraints

Counting sort is efficient when:

$$
k = O(n)
$$

If $k \gg n$, memory and time become inefficient.

## When to Use

Use counting sort when:

* keys are integers in a small range
* stability is required
* linear time is needed
* comparison sorting overhead is too high

It is often used as a building block in radix sort.

## Implementation (Go)

```id="t4m1qp"
func CountingSort(a []int, k int) []int {
    count := make([]int, k+1)

    for _, v := range a {
        count[v]++
    }

    result := make([]int, len(a))
    idx := 0

    for v := 0; v <= k; v++ {
        for count[v] > 0 {
            result[idx] = v
            idx++
            count[v]--
        }
    }

    return result
}
```