Counting Sort
Sorting: lesson 7 of 10
Skip comparisons entirely when the values are small.
Lesson 7 of 10 · 5 min
Counting Sort
Step 1 of 17
value 0 · 0
value 1 · 0
value 2 · 0
value 3 · 0
3
1
3
0
2
1
3
Counting sort never compares two values. It only needs to know the range — here every value is 0 to 3.
The Idea
If the values come from a small known range, count how many times each one appears, then read the counts back out in order. That is O(n + k), faster than any comparison sort, but only for that shape of data.
Real-World Example
Tallying T-shirt sizes for a conference. Nobody ever compares two shirts. You count how many S, M, L, and XL were ordered, then pack the boxes in size order straight from the tally sheet.
The Code
def counting_sort(nums, max_value):
counts = [0] * (max_value + 1)
for x in nums:
counts[x] += 1 # tally each value
out = []
for value, times in enumerate(counts):
out.extend([value] * times) # read the tallies in order
return out
print(counting_sort([3, 1, 3, 0, 2], 3)) # [0, 1, 2, 3, 3]Your turn
What does this print?
nums = [2, 0, 2, 1]
counts = [0] * 3
for x in nums:
counts[x] += 1
print(counts)Mini quiz
1 / 3