0

Counting Sort

Medium

Tally how many times each key appears, turn the tally into positions with a prefix sum, then place elements from the back to stay stable.

non comparisonstablelinear
TimeO(n + k)
SpaceO(n + k)
InputSmall non-negative integers
4
0
2
1
2
2
8
3
3
4
3
5
1
6
count
0
0
0
0
0
0
0
0
0

Start with an empty tally for every possible key.

1 / 24
count[v]++ for each v
prefix sum over count
for i from n-1 down to 0:
out[--count[a[i]]] = a[i]
Why it matters

Beats the n log n bound because it never compares two elements. Needs a small integer key range.

Practise this
Sort ColorsMCounting SortE
Keyboard
space play← → stepr restartctrl K search

More in Sorting

Quickselect
O(n) expected, O(n^2) worst
Bubble Sort
O(n^2), best O(n) when already sorted
Selection Sort
O(n^2) always
Insertion Sort
O(n^2), O(n) on nearly sorted input
Merge Sort
O(n log n) always
Quick Sort
O(n log n) average, O(n^2) worst
Next visualiser
Reverse a Linked List