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.65
0.12
0.44
0.67
0.52
0.13
0.83
0.31
0.72
0.98
0.45
0.22
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