Bucket sort distributes elements into k buckets by value, sorts each bucket, then concatenates. It runs in O(n+k) average time when elements are roughly uniformly distributed across the range — but degrades to O(n²) if every element lands in one bucket.
Unlike quicksort or merge sort, bucket sort does not rely only on comparing pairs of elements. It uses the value of each element to decide where it goes, which is how it escapes the O(n log n) lower bound for comparison sorting. The price is an assumption about the input: the values must be spread fairly evenly over a known range.
The correctness argument is simple: every value in bucket i is smaller than every value in bucket i+1, because each bucket owns a contiguous slice of the range. So once each bucket is internally sorted, reading buckets left to right produces a fully sorted sequence. The speed argument depends on the distribution: if n values are spread uniformly over k = n buckets, the expected size of each bucket is constant, so sorting all buckets costs O(n) in expectation even with a quadratic per-bucket sort.
| Best | Average | Worst | Space (Worst) |
|---|---|---|---|
Ω(n+k) |
Θ(n+k) |
O(n²) |
O(n) |
Determine the input range [lo, hi). Create k buckets, mapping each element to bucket index floor((x - lo) / (hi - lo) * k). Sort each bucket (typically with insertion sort, which is fast on small inputs). Concatenate the buckets in order. Works best when k ≈ n and inputs are uniform.
def bucket_sort(arr, k=None):
"""Bucket sort for numeric input. Falls back to insertion sort per bucket."""
if not arr:
return arr
if k is None:
k = len(arr)
lo, hi = min(arr), max(arr)
if lo == hi:
return list(arr)
buckets = [[] for _ in range(k)]
span = (hi - lo) / k
for x in arr:
idx = min(int((x - lo) / span), k - 1)
buckets[idx].append(x)
out = []
for b in buckets:
# insertion sort on each small bucket
for i in range(1, len(b)):
v = b[i]; j = i - 1
while j >= 0 and b[j] > v:
b[j + 1] = b[j]; j -= 1
b[j + 1] = v
out.extend(b)
return out
print(bucket_sort([0.42, 0.32, 0.23, 0.52, 0.25, 0.47]))With lo = 0.23, hi = 0.52 and six buckets, each bucket spans about 0.048. The value 0.42 maps to index int(0.19 / 0.048) = 3; 0.52, the maximum, would map to 6 and is clamped to 5 by the min(..., k - 1) guard. Only bucket 0 receives two values, so insertion sort does one comparison there; the gather step then emits buckets 0 through 5 in order.
The implementation above sorts floats in place inside each bucket. When the records carry a key and other data, it is usually cleaner to sort each bucket with Python's built-in sorted, which is stable and runs in O(m log m) for a bucket of size m. That bounds the worst case at O(n log n) instead of O(n²) while keeping the O(n) average:
def bucket_sort_by(items, key, k=None):
"""Stable bucket sort of arbitrary records by a numeric key."""
if len(items) < 2:
return list(items)
k = k or len(items)
keys = [key(x) for x in items]
lo, hi = min(keys), max(keys)
if lo == hi:
return list(items)
width = (hi - lo) / k
buckets = [[] for _ in range(k)]
for item, kv in zip(items, keys):
buckets[min(int((kv - lo) / width), k - 1)].append(item)
out = []
for b in buckets:
out.extend(sorted(b, key=key)) # Timsort: stable, O(m log m) worst case
return out
people = [("ana", 31.5), ("bo", 22.0), ("cy", 31.5), ("di", 45.2)]
print(bucket_sort_by(people, key=lambda p: p[1]))
# [('bo', 22.0), ('ana', 31.5), ('cy', 31.5), ('di', 45.2)]Other variants include histogram sort, which counts bucket sizes first and writes into one preallocated array instead of lists; generic bucket sort used as the first pass of a parallel sort, where each bucket is sent to a different worker; and bucketing on the top bits of an integer, which turns into most-significant-digit radix sort when applied recursively.
When to use it. Reach for bucket sort when keys are numeric, bounded, and close to uniform, such as normalized scores, random hashes, or timestamps within a window. It also suits external and distributed sorting, because buckets can be written to separate files or machines and sorted independently. For general-purpose in-memory sorting in Python, the built-in Timsort is usually faster in practice because it runs in C.
IndexError.