Bucket Sort: Partitioning the Range
What you'll learn: How bucket sort distributes elements into separate "buckets" based on their value ranges to achieve fast sorting under the right conditions.
The Core Idea
Bucket sort works by dividing the input range into several intervals called buckets, distributing elements into these buckets based on their values, sorting each bucket individually, and then concatenating all buckets in order.
Think of organizing a deck of cards: instead of sorting all 52 cards at once, you first separate them into four suit piles (hearts, diamonds, clubs, spades), sort each pile, then combine them. Each suit is a "bucket."
How It Works
- Determine the range: Find the minimum and maximum values in your data
- Create buckets: Divide this range into equal-sized intervals (buckets)
- Distribute: Place each element into the appropriate bucket based on its value
- Sort buckets: Sort each bucket individually (often using insertion sort for small buckets)
- Concatenate: Merge all buckets back together in order
When Bucket Sort Shines
Bucket sort achieves average-case O(n) time when:
- Input is uniformly distributed across the range
- You use an appropriate number of buckets (often n buckets for n elements)
- Elements spread evenly, so each bucket stays small
If all elements land in one bucket, performance degrades to whatever algorithm you use to sort that bucket—potentially O(n²).
Practical Example
Sorting student grades (0-100): create 10 buckets for ranges [0-9], [10-19], ..., [90-100]. A grade of 87 goes into bucket 8, a grade of 42 into bucket 4. Sort each bucket, then concatenate.
Key Takeaway: Bucket sort partitions the input range into intervals, distributing elements accordingly to achieve linear average-case time when data is uniformly distributed.