Bucket Sort distributes uniformly random numbers into buckets by range, sorts each bucket (often with insertion sort), and concatenates them. It performs well when inputs are evenly distributed.
Phase: Distribute into buckets based on value in [0,1)
Array
0.03
0.97
0.87
0.11
0.24
0.08
0.19
0.75
0.31
0.80
0.50
0.74
Buckets [0,1) split into 6 ranges
Bucket 0 (≈ [0.00, 0.17))
empty
Bucket 1 (≈ [0.17, 0.33))
empty
Bucket 2 (≈ [0.33, 0.50))
empty
Bucket 3 (≈ [0.50, 0.67))
empty
Bucket 4 (≈ [0.67, 0.83))
empty
Bucket 5 (≈ [0.83, 1.00))
empty
Complexity
Expected Time: O(n + k)
Worst Time: O(n²) if buckets become imbalanced
Space: O(n + k)
Stable: Yes (if in-bucket sort is stable)
Notes
Assumes near-uniform distribution in [0,1)
Commonly used as a building block for specialized domains