Distribution sorts · Intermediate
Bucket Sort
Distribute values into ordered ranges, sort inside each bucket, then concatenate.
- Best
- O(n + k)
- Average
- O(n + k)
- Worst
- O(n²)
- Space
- O(n + k)
- Stability
- Stability depends on the implementation
- Memory model
- Uses auxiliary storage
How it builds order
- Map every value to a range bucket.
- Sort each bucket locally.
- Visit buckets from low range to high.
- Concatenate their contents.
Why it works
Bucket ranges guarantee that every item in an earlier bucket belongs before every item in a later bucket.
Watch for: Performance depends on even distribution; one overloaded bucket recreates a hard sorting problem.
The interactive version of this page adds the full trace, synchronized pseudocode, practice decisions, input experiments, and mastery review.