SortingSorting

Counting Sort

Count occurrences of each key in a small integer range, then place elements by prefix sums — linear time, no comparisons.

Learn Counting Sort →
a
4
0
2
1
2
2
8
3
3
4
3
5
1
6
0
7
4
8
value
0
0
1
1
2
2
3
3
4
4
5
5
6
6
7
7
8
8
count
0
0
0
1
0
2
0
3
0
4
0
5
0
6
0
7
0
8
out
0
1
2
3
4
5
6
7
8
1/29Values range from 0 to k=8. Counting sort avoids comparisons entirely: it tallies how often each value occurs.
Element being processedCount slot updatedPlaced in output
PseudocodeLearn Counting Sort →
1k = max(a); count = [0] * (k+1)
2for x in a: count[x] += 1
3for v in 1 .. k: count[v] += count[v-1]   # prefix sums
4for x in reversed(a):
5  count[x] -= 1
6  out[count[x]] = x
7copy out into a
Variables
n9
k8
Complexity
best O(n + k)
avg O(n + k)
worst O(n + k)
space O(n + k)
Speed