Counting Sort and Bucket Sort
28 min · Intermediate
Need help? Ask a tutor on WhatsApp (opens in a new tab)A sort that never compares two values can beat the O(n log n) limit. It works when the values are small whole numbers or spread evenly, which is common with marks, ratings and ages.
Counting sort: count, do not compare
Counting sort is a non-comparison sort for whole numbers in a small range: it counts how often each value occurs, then writes the values out in order, in O(n + k) time for range size k.
When the values are small whole numbers, such as marks from 0 to 100, do not compare at all. Count how many times each value appears, then write the values out in order.
def counting_sort(values, max_value): counts = [0] * (max_value + 1) for v in values: counts[v] += 1 result = [] for number, how_many in enumerate(counts): result.extend([number] * how_many) return resultExample 1 · Counting marks
marks = [4, 2, 2, 8, 3, 3, 1]counts = [0] * 10for m in marks: counts[m] += 1print(counts)print([n for n, how_many in enumerate(counts) for _ in range(how_many)])[0, 1, 2, 2, 1, 0, 0, 0, 1, 0] [1, 2, 2, 3, 3, 4, 8]
What this code does
- The slot at index 3 holds 2 because the mark 3 appears twice.
- Reading the counts from index 0 upwards gives the values in sorted order.
Example 2 · Negative numbers: shift by the minimum
temperatures = [3, -2, 0, -2, 5, -1]low = min(temperatures)counts = [0] * (max(temperatures) - low + 1)for t in temperatures: counts[t - low] += 1result = []for offset, how_many in enumerate(counts): result.extend([offset + low] * how_many)print(result)[-2, -2, -1, 0, 3, 5]
What this code does
- Subtracting the minimum maps -2 to slot 0, so every index is valid.
- Adding
lowback gives the original value.
Example 3 · Counter does the counting for you
from collections import Counter
marks = [4, 2, 2, 8, 3, 3, 1]counts = Counter(marks)print([value for value in range(max(marks) + 1) for _ in range(counts[value])])[1, 2, 2, 3, 3, 4, 8]
What this code does
Counterreturns 0 for a missing value, so the loop over the range stays simple.- It also works without a fixed upper bound if you loop over
sorted(counts)instead.
With n values in the range 0 to k, the time is O(n + k) and the space is O(k). Comparison sorts cannot beat O(n log n), but counting sort is not a comparison sort.
A stable counting sort for records
To sort records by a small whole-number key, turn the counts into start positions with a running total. Then place each record at its start slot, left to right, so equal keys keep their order.
def counting_sort_by(records, key, max_key): counts = [0] * (max_key + 2) for record in records: counts[key(record) + 1] += 1 for k in range(max_key + 1): counts[k + 1] += counts[k] out = [None] * len(records) for record in records: out[counts[key(record)]] = record counts[key(record)] += 1 return outExample 4 · Stable counting sort of records
def counting_sort_by(records, key, max_key): counts = [0] * (max_key + 2) for record in records: counts[key(record) + 1] += 1 for k in range(max_key + 1): counts[k + 1] += counts[k] out = [None] * len(records) for record in records: out[counts[key(record)]] = record counts[key(record)] += 1 return out
tickets = [("T1", 2), ("T2", 0), ("T3", 2), ("T4", 1), ("T5", 0)]result = counting_sort_by(tickets, lambda t: t[1], 2)print([name for name, priority in result])['T2', 'T5', 'T4', 'T1', 'T3']
What this code does
- Tickets T2 and T5 share priority 0 and keep their order. So do T1 and T3 at priority 2.
- The
keyfunction lets the same code sort any record by a small whole number.
The first loop counts, the second makes start positions, the third places records. It stays stable because records are placed in input order.
Bucket sort: spread, then sort each bucket
Bucket sort is a sort that distributes values into buckets by range, sorts each bucket on its own, and joins the buckets in order. It is fast when the values are spread evenly.
When values are spread evenly over a known range, drop each one into a bucket for its part of the range, sort each small bucket, and join the buckets in order.
def bucket_sort(values): n = len(values) buckets = [[] for _ in range(n)] for v in values: buckets[int(v * n)].append(v) result = [] for bucket in buckets: result.extend(sorted(bucket)) return resultExample 5 · Bucket sort on evenly spread values
def bucket_sort(values): n = len(values) buckets = [[] for _ in range(n)] for v in values: buckets[int(v * n)].append(v) result = [] for bucket in buckets: result.extend(sorted(bucket)) return result
print(bucket_sort([0.78, 0.17, 0.39, 0.26, 0.72, 0.94, 0.21, 0.12, 0.23, 0.68]))[0.12, 0.17, 0.21, 0.23, 0.26, 0.39, 0.68, 0.72, 0.78, 0.94]
What this code does
- With 10 values, the bucket number is
int(v * 10), so 0.78 goes to bucket 7. - Most buckets hold one or two values, so sorting them is nearly free.
This version expects floats from 0 up to but not including 1. With an even spread each bucket holds about one value, so the time is O(n) on average. If all values land in one bucket, it is as slow as the inner sort.
When the range is too big
Radix sort is a sort for whole numbers that sorts by one digit at a time, from the least significant digit to the most, using a stable sort such as counting sort for each digit.
Counting sort needs one slot for each possible value. Two values such as 3 and 1000000 would need a million slots, so the range must be small compared with n. Radix sort fixes this by sorting one digit at a time.
Example 6 · Radix sort, one digit at a time
def radix_sort(values): place = 1 while place <= max(values): buckets = [[] for _ in range(10)] for v in values: buckets[(v // place) % 10].append(v) values = [v for bucket in buckets for v in bucket] place *= 10 return values
print(radix_sort([170, 45, 75, 90, 802, 24, 2, 66]))[2, 24, 45, 66, 75, 90, 170, 802]
What this code does
- Each round is a stable bucket pass on one digit: ones, then tens, then hundreds.
- Stability is what makes the earlier digits count as tie breakers. With d digits the time is O(d * (n + 10)).
Example 7 · Too many empty slots
values = [3, 1000000]counts = [0] * (max(values) + 1)print(len(values), "values need", len(counts), "slots")print(sorted(values))2 values need 1000001 slots [3, 1000000]
What this code does
- Two values need a million slots, so counting sort is a poor fit here.
sorted()uses no extra range at all, so choose it when the range is big.
Next step
Check your understanding
11 quick questions