What is Bucket Sort?
Learn how bucket sort scatters data into range buckets and sorts each locally for near-linear time on uniform data.
Expected Interview Answer
Bucket sort distributes elements from a roughly uniformly distributed input into a fixed number of buckets by value range, sorts each bucket individually with a simple algorithm like insertion sort, then concatenates the buckets in order, achieving expected O(n + k) time when the data is well spread across the range.
Each element’s value determines which bucket it lands in, typically via a formula like bucket_index = floor(value * num_buckets / max_value), so the buckets themselves come out coarsely ordered by construction. Because a well-distributed input spreads roughly n/k elements per bucket, sorting each bucket with insertion sort costs a small constant amount of work per bucket on average, and the total across all buckets stays close to O(n) plus the O(k) overhead of creating the buckets. Concatenating the sorted buckets front to back then yields the fully sorted output. The catch is that bucket sort’s performance depends entirely on the input being roughly uniformly distributed; a skewed input that dumps most elements into one bucket degrades toward the O(n log n) or O(n^2) cost of whatever algorithm sorts that overloaded bucket.
- Expected O(n + k) time on uniformly distributed data
- Parallelizable — each bucket can be sorted independently
- Works naturally for floating point values in a known range
- Degrades gracefully to the bucket’s inner sort algorithm on skewed data
AI Mentor Explanation
A groundstaff crew sorting a season of batting averages, which cluster fairly evenly between 0 and 100, first tosses each score into one of ten labeled bins by tens digit, so scores in the 40s all land together regardless of order. Each bin then only needs a quick local sort, since it holds a small handful of scores rather than the whole season. Lining the bins up from lowest to highest and reading them in order produces the fully sorted season averages. This only stays fast because batting averages spread out fairly evenly across the range — if every player somehow averaged in the 90s, one bin would swell and the local sort inside it would dominate the total time.
Step-by-Step Explanation
Step 1
Create k empty buckets
Choose a bucket count k, typically close to n, covering the known value range.
Step 2
Scatter elements into buckets
Map each value to a bucket index using its position within the overall range, in a single O(n) pass.
Step 3
Sort each bucket locally
Apply a simple algorithm like insertion sort to each bucket, which is cheap since buckets are small on average.
Step 4
Concatenate the buckets in order
Walk the buckets from lowest range to highest and append their sorted contents to produce the final sorted array.
What Interviewer Expects
- Explain how the bucket index formula distributes elements by value range
- State the expected O(n + k) time under a roughly uniform distribution
- Identify the worst case, where a skewed distribution overloads one bucket
- Name a real use case, such as sorting floating-point values in [0, 1)
Common Mistakes
- Assuming bucket sort is always O(n) regardless of the input distribution
- Forgetting that a bad distribution degrades to the inner sort’s complexity on the overloaded bucket
- Confusing bucket sort with counting sort (bucket sort ranges cover intervals, not exact discrete values)
- Choosing too few buckets, causing most elements to collide into the same bucket
Best Answer (HR Friendly)
“Bucket sort works by scattering values into a set of range-based buckets, sorting each small bucket quickly, and then stitching the buckets back together in order. It is fast on average, close to linear time, but only when the data is fairly evenly spread across the range, since a lopsided distribution just pushes the cost into whichever bucket ends up overloaded.”
Code Example
def bucket_sort(arr):
n = len(arr)
buckets = [[] for _ in range(n)]
for value in arr:
index = int(value * n)
buckets[index].append(value)
for bucket in buckets:
bucket.sort() # insertion sort in practice for small buckets
result = []
for bucket in buckets:
result.extend(bucket)
return resultFollow-up Questions
- What happens to bucket sort’s performance on heavily skewed data?
- How would you choose the number of buckets for a given dataset?
- How is bucket sort different from counting sort and radix sort?
- Why is insertion sort a good choice for sorting each individual bucket?
MCQ Practice
1. What is bucket sort’s expected time complexity on a uniformly distributed input?
With elements spread evenly across k buckets, scattering plus small per-bucket sorts costs an expected O(n + k).
2. What causes bucket sort to degrade toward its worst-case performance?
If most elements land in one bucket, that bucket’s local sort dominates the runtime, pushing it toward that inner sort’s worst case.
3. What is typically used to sort the contents of each individual bucket?
Because buckets are small on average, insertion sort’s low overhead makes it the common choice for the per-bucket sort.
Flash Cards
What is bucket sort’s expected time complexity? — O(n + k) when the input is roughly uniformly distributed across k buckets.
How does bucket sort assign elements to buckets? — By mapping each value’s position within the known range to a bucket index.
What causes bucket sort to perform poorly? — A skewed distribution that overloads one bucket, pushing cost toward that bucket’s inner sort complexity.
What sort is commonly used inside each bucket? — Insertion sort, since buckets are usually small on average.