Counting & Radix Sort
DSA · Intermediate
Definition
Counting sort counts occurrences of each value; radix sort sorts digit by digit using a stable counting sort.
Beats O(n log n) when values lie in a small range.
Diagram
Flowchart
Example: Counting sort
a = [3, 1, 3, 2]
c = [0] * 4
for x in a: c[x] += 1
print([v for v in range(4) for _ in range(c[v])])Output: [1, 2, 3, 3]
Complexity
O(n + k) where k = value range
Key points
- Not comparison-based
- Needs integer-like keys
Interview questions
When is counting sort bad?
When the value range k is huge compared to n.