DSA · Reimagined
JSON All
Sorting medium time O(n + k) space O(n + k)

Counting Sort

For small non-negative integers, count how many of each value there are, turn the counts into end positions with a running sum, then place each input value where it belongs. Stable and comparison-free.

input
4
0
2
1
2
2
8
3
3
4
3
5
1
6
counts (index = value)
0
0
0
1
0
2
0
3
0
4
0
5
0
6
0
7
0
8
output
0
1
2
3
4
5
6

Counting sort: tally every value, then place them all in order.

1 / 17

Practice

Machine twin: /dsa-viz-v2/counting-sort.json — the full deterministic run as structured data.