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.
| 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]))