Counting Sort
DSA · Sorting Algorithms
Theory
Counting sort does not compare elements. It counts how many times each value occurs in a known small range, then rebuilds the sorted output from those counts. It runs in O(n + k) time, where k is the range of values, which beats O(n log n) when k is small.
Why we use it
It sorts integers with a small range in linear time.
When to use it
Use it for ages, exam marks (0-100), ratings, or any integers with a limited range. Avoid it when values are spread over a huge range.
How it works
- Find max value k
- Create count array of size k + 1
- For each value x: count[x] += 1
- For v = 0..k: output v, count[v] times
- Sorted output in O(n + k)
Syntax
count = [0] * (max+1)
for x in arr: count[x] += 1
rebuild: for v, c in enumerate(count): output c copies of v
Time: O(n + k) Space: O(k) Stable version possibleExample
def counting_sort(arr):
if not arr:
return arr
count = [0] * (max(arr) + 1)
for x in arr:
count[x] += 1
result = []
for value in range(len(count)):
result += [value] * count[value]
return result
marks = [4, 2, 2, 8, 3, 3, 1, 9, 4]
print(counting_sort(marks))Key points
- No comparisons between elements
- O(n + k) where k is the value range
- Only for integers in a small range
- Basis of radix sort