1. One-Liner
Counting Sort counts how many times each integer key appears, computes prefix sums, then writes each value into its correct slot in one pass.
2. The Problem It Solves
When keys are integers in a bounded range [0, k], you can sort in O(n + k) time — faster than comparison lower bounds — without comparing elements pairwise.
3. The Core Idea
Imagine ballot boxes labeled 0..k: first count votes per label, then walk labels in order and spill each count back into the output array.
4. How It Works (Step-by-Step)
| Step | What Happens |
|---|---|
| 1. | Allocate count[0..k] initialized to 0 |
| 2. | For each x in input, count[x]++ |
| 3. | Prefix sum count[i] += count[i-1] → ending positions |
| 4. | Walk input backwards (for stability); place each x at count[x]-1, decrement count[x] |
5. Dry Run Example
Keys in [0,3]: data [2, 0, 2, 3] → counts [1,0,2,1] → prefix → stable scatter → [0, 2, 2, 3].
6. Key Properties
| Property | Value |
|---|---|
| Comparison-free | Uses key as index |
| Stable | Yes if backward pass used |
| Space | O(k) extra |
7. Where It Is Used
| Company / System | How They Use It |
|---|---|
| Radix sort subroutine | Per-digit bucket |
| GPU / parallel | Small alphabet histograms |
8. Interview Tips
Explain why backward pass for stability; when k >> n it is a bad idea; link to Radix.
9. Comparison with Other Algorithms
| Algorithm | Needs | Time | Comparison-based |
|---|---|---|---|
| Counting | Bounded integer keys | O(n+k) | No |
| Merge | General | O(n log n) | Yes |
10. Complexity
| Metric | Value |
|---|---|
| Time (Best) | O(n + k) |
| Time (Average) | O(n + k) |
| Time (Worst) | O(n + k) |
| Space | O(n + k) auxiliary |
| Stable? | Yes (typical stable impl) |
Implementation Example (PYTHON)
def counting_sort(arr, k):
count = [0] * (k + 1)
for x in arr:
count[x] += 1
for i in range(1, k + 1):
count[i] += count[i - 1]
out = [0] * len(arr)
for x in reversed(arr):
count[x] -= 1
out[count[x]] = x
return out