Counting Sort never compares elements. Instead, it counts how often each value appears, then uses those counts to compute exactly where each value belongs.

By sidestepping comparisons, it beats the O(n log n) lower bound of comparison sorts — running in O(n + k), where k is the range of possible values. The catch: it only works on integers (or categorical keys) with a small range.

How It Works

1. Find the minimum and maximum values to determine the key range K.
2. Build a count array of size K and tally the frequency of each element.
3. Convert count into prefix sums — each position now holds the number of elements ≤ that value, which is the last output index it can occupy.
4. Iterate the input backward, placing each element into output at the position given by its prefix-sum entry, then decrement that entry.
5. The backward pass is what makes the sort stable.

Key Insight

The prefix-sum array is the whole trick. After cumulation, count[v] answers “how many elements are ≤ v?” Subtract 1 to get the rightmost output slot for value v.

Walking the input backward and decrementing each slot keeps equal values in their original relative order — stability for free. That is exactly why Radix Sort uses Counting Sort as its stable building block.

Worked Example

Sort [4, 1, 3, 4, 3] (values 1–4):

1. Count: count[1]=1, count[2]=0, count[3]=2, count[4]=2.
2. Prefix sums: count[1]=1, count[2]=1, count[3]=3, count[4]=5.
3. Place backward: 3 → index count[3]−1 = 2 → output[2]=3; next 4 → index 4 → output[4]=4; 3 → index 1 → output[1]=3; 1 → index 0 → output[0]=1; 4 → index 3 → output[3]=4.

Result: output = [1, 3, 3, 4, 4]. Watch the visualizer highlight the two 3s and the two 4s — the backward placement preserves their original order.

Edge Cases & Pitfalls

• Huge range — if max - min is enormous (e.g., 0 to 10⁹), the count array is unaffordable. Use Radix Sort instead.
• Floating-point values — no discrete keys to count: not applicable.
• Negative values — shift keys by min (count[value - min]), as the pseudocode does.
• Stability matters — always use the backward pass; a forward pass with the same prefix sums is not stable.
• Sparse data — if n is small but k is large, the O(k) count array dominates the cost.

Comparison With Other Sorts

Applications

• Sorting integer ranges like test scores, ages, or character frequencies (k small)
• Radix Sort’s stable sub-sort
• When the range is bounded and k is comparable to n — a true linear sort

Practice Trajectory

1. Hand-trace Counting Sort on [3, 1, 2, 3, 1], writing count, prefix-sum, and output arrays.
2. Explain why the backward pass is required for stability, and show the instability of a forward pass.
3. Construct a range where Counting Sort is slower than merge sort despite being “linear”.
4. Describe how to shift negative keys and why count[value - min] works.
5. Implement Counting Sort, then use it as a stable digit pass inside a simple 2-digit Radix Sort.