1. One-Liner
Bucket Sort maps each value to a bucket index, sorts inside small buckets, then concatenates buckets in order.
2. The Problem It Solves
For inputs uniformly spread across an interval (often [0,1) floats), average time can be O(n) with a simple bucketing map plus a tiny sort per bucket.
3. The Core Idea
Throw socks into labeled laundry bins by size range, sort each bin quickly, then empty bins 1, 2, 3… in order.
4. How It Works (Step-by-Step)
| Step | What Happens |
|---|---|
| 1. | Create n empty buckets (common choice) |
| 2. | Map each x to bucket ⌊n · normalize(x)⌋ (clamped) |
| 3. | Sort each bucket (insertion sort) |
| 4. | Concatenate buckets |
5. Dry Run Example
Uniform keys in [0,1): bucket boundaries split [0,0.25), [0.25,0.5), …; after per-bucket sort, concatenate → sorted.
6. Key Properties
| Property | Value |
|---|---|
| Average | O(n) under uniform input assumptions |
| Worst | O(n²) if all keys land in one bucket |
| Stable | Depends on bucket sort choice |
7. Where It Is Used
| Company / System | How They Use It |
|---|---|
| Graphics / histograms | Binning + order |
| External tools | When distribution is known near-uniform |
8. Interview Tips
State assumptions clearly; contrast worst case with Merge; mention map to index formula.
9. Comparison with Other Algorithms
| Algorithm | Average | Worst | Needs |
|---|---|---|---|
| Bucket | O(n) | O(n²) | Good spread |
| Counting | O(n+k) | O(n+k) | Small integer range |
10. Complexity
| Metric | Value |
|---|---|
| Time (Best) | O(n + k) (bucket overhead) |
| Time (Average) | O(n) uniform, O(n) buckets |
| Time (Worst) | O(n²) |
| Space | O(n + k) buckets |
| Stable? | Can be (with stable bucket sort) |
Implementation Example (PYTHON)
def bucket_sort(arr):
if not arr:
return arr
n = len(arr)
lo, hi = min(arr), max(arr)
if lo == hi:
return arr
buckets = [[] for _ in range(n)]
for x in arr:
i = int((x - lo) / (hi - lo) * (n - 1))
buckets[i].append(x)
out = []
for b in buckets:
b.sort()
out.extend(b)
return out