What are bucket sort's three phases, and what must be true of the data for it to run in linear time?
answer
- three phases, and only one of them sorts
- the key's value picks the slot
- with n buckets, how full is each one?
- no merge needed at the end — why not?
- linear is an expectation, not a guarantee
basics
~20 sBucket sort scatters keys into range-partitioned buckets by value, sorts each bucket with a simple sort, then concatenates the buckets in order. Expected linear time holds only when the keys spread evenly, leaving every bucket tiny.
solid answer
~50 sBucket sort is a distribution sort with three phases. **Scatter**: for keys known to lie in a range — say normalized similarity scores in `[0.0, 1.0)` — compute a bucket index arithmetically from each key's value, `floor(k * x)` for `k` buckets, and drop the key there; this is O(n) and does no comparisons. **Sort each bucket**, typically with insertion sort because the buckets are expected to be tiny. **Gather**: concatenate bucket 0, bucket 1, … in order, which is O(n + k) and needs no merging, because every key in bucket `i` is already less than every key in bucket `i+1`. The linear bound is an *expectation* over a benign distribution: with `k = n` and keys spread evenly, each bucket holds about one element, so the inner sorts total O(n). Skew the input and one bucket swallows the data, and the inner sort's cost becomes the whole cost.
code
pseudocode · 13 linesn = length(a)
for i in 0..n-1:
B[i] = empty list // n buckets, bucket i owns [i/n, (i+1)/n)
for i in 0..n-1:
idx = floor(n * a[i]) // the value picks the slot; no comparison here
insert a[i] into B[idx]
for i in 0..n-1:
insertion_sort(B[i]) // each bucket is expected to be tiny
out = empty list
for i in 0..n-1:
for each x in B[i]:
insert x at end of out // buckets are already in range order
return outgo deeper
Be ready to name the three phases in order — scatter by value, sort each bucket, concatenate — and to say plainly that the linear cost depends on the keys spreading out rather than piling into one bucket.
Explain where the expected O(n) actually comes from: with roughly as many buckets as keys and an even spread, each bucket holds about one element, so the inner sorts add up to linear work. Explain why no merge is needed.
Show that you treat the distribution as an input you must verify, not an assumption you inherit. Mention the O(n + k) memory, the index-clamping boundary, and that independent buckets make phase two easy to parallelize.
Own the framing that this algorithm trades a universal guarantee for a conditional one. Be able to say when a team should accept a data-dependent sort at all, and what evidence about the data you would require before it lands in shared code.
### The shape of the algorithm Bucket sort belongs to the *distribution* family: instead of asking "is this key less than that one?", it uses the key's **value** to compute where the key belongs. It needs two things up front — a known key range, and buckets that partition that range in sorted order. Take a concrete workload: `n` normalized similarity scores, each a real number in `[0.0, 1.0)`. Allocate `k` empty buckets, each owning a slice of the range. With `k = n`, bucket `i` owns `[i/n, (i+1)/n)`. 1. **Scatter.** For each key `x`, compute `idx = floor(n * x)` and insert `x` into bucket `idx`. One arithmetic operation per key: O(n), zero comparisons. 2. **Sort each bucket.** Each bucket is expected to be tiny, so a simple quadratic sort with small constants — insertion sort is the classic choice — is used rather than a general-purpose sort with heavier setup. 3. **Gather.** Concatenate the buckets in index order. No merge step is needed: because the buckets partition the range in order, everything in bucket `i` is already ≤ everything in bucket `i+1`. Cost O(n + k). | Phase | Cost | |---|---| | Allocate buckets | O(k) | | Scatter | O(n) | | Sort buckets | sum of the inner sort's cost over each bucket | | Gather | O(n + k) | Only the third row is data-dependent, and that row is the whole story. ### Where the linear expectation comes from If the inner sort is quadratic in a bucket of size `m`, the total inner work is proportional to the **sum of squared bucket sizes**. Under a uniform distribution with `k = n`, the expected value of that sum is Θ(n) — each bucket's expected squared occupancy is `2 - 1/n`, a constant. Add the O(n) scatter and O(n + k) gather and the expected total is Θ(n). Read the direction of that claim carefully. It is an **expectation under an assumed distribution**, not a worst-case bound and not a promise about any single run. Every algorithm here still has a worst case: put all `n` keys in one bucket and the quadratic inner sort runs on all of them, giving O(n²). ### Why this does not break the comparison lower bound The Ω(n log n) lower bound applies to algorithms whose **only** source of information about the data is pairwise comparison. Bucket sort does compare — inside each bucket — but the scatter step extracts information no comparison could give it: it does arithmetic on the key's numeric value to derive a position. That is the escape hatch, the same one counting and radix sort use. A candidate who says "bucket sort is O(n) because it never compares anything" has the mechanism wrong; it compares plenty, just over tiny sets. ### Boundaries and engineering details worth knowing - **The index boundary.** `floor(k * x)` produces `k` — one past the last bucket — for a key sitting exactly at the top of the declared range. Either declare the range half-open and enforce it, or clamp: `idx = min(k - 1, floor(k * x))`. This is the single most common bug in a hand-written scatter. - **Stability.** Bucket sort is stable if the scatter appends equal keys in input order and the inner sort is stable; concatenation preserves the order it is handed. Nothing about the structure forces stability, so it is a property of your implementation, not of the algorithm's name. - **Space.** It is not in-place: O(n + k) auxiliary space for the buckets and their contents. That footprint is often the reason it loses to an in-place comparison sort even when the asymptotics look better. - **Independence.** The buckets are independent after the scatter, which makes phase two trivially parallelizable — a real practical argument in its favour, separate from the asymptotics. - **Keys that are not numbers.** Any key you can map monotonically onto a numeric range works — a monotone mapping is required, otherwise the gather no longer produces sorted output. ### The one sentence to leave the interviewer with Bucket sort is the sort whose admission ticket is a **distribution assumption**. Merge sort's O(n log n) is true for every input; bucket sort's O(n) is true for inputs that spread. If you cannot say what the distribution is, you cannot claim the bound.
- In the scatter step, what happens to a key that sits exactly at the top of the declared range?`floor(k * x)` returns `k`, one past the last bucket, and the write goes out of bounds. Fix it by declaring the range half-open and validating input, or by clamping the index to `min(k - 1, floor(k * x))`. It is the classic off-by-one in a hand-rolled scatter, and it only fires on the single largest possible key, so it survives casual testing.
- Is bucket sort stable?It can be, but not automatically. It is stable when the scatter appends equal keys to the end of their bucket in input order and the per-bucket sort is itself stable; the gather then just concatenates and preserves that order. Swap in an unstable inner sort, or scatter by prepending, and stability is gone. Stability here is a property of the implementation, not of the algorithm's name.
- Why is no merge step needed after the buckets are sorted?Because the buckets partition the key range in ascending order: every key in bucket `i` is less than every key in bucket `i+1` by construction of the index function. So the concatenation is already sorted, and the gather is a linear copy rather than a k-way merge. This is what separates bucket sort from merge sort's divide-and-conquer, where the split carries no ordering information and the merge does all the work.
Sorting mail by dropping each letter into a pigeonhole for its street-number range, ordering the handful in each pigeonhole, then sweeping the pigeonholes left to right. It only saves time if no single pigeonhole swallows the whole delivery.
saying these in an interview costs you the question
- Says bucket sort is O(n), with no conditions attached
- Claims bucket sort performs no comparisons at all
- Assumes buckets end up equal in size after the scatter
- Thinks the sorted buckets still need a k-way merge
- Describes it as in-place, ignoring the O(n + k) buckets