Bucket Sort: Sorting by Scattering and Gathering

The core idea: scatter, sort locally, gather

Bucket sort belongs to the family of distribution sorts — the same family as counting sort and radix sort — that sidestep the Ω(n log n) comparison lower bound by using key values as addresses rather than only comparing them. The plan is three moves:

• Scatter. Partition the value range into k buckets (usually k = n) and drop each element into the bucket its value maps to. For keys in [0, 1) with k = n buckets, element x goes to bucket ⌊n·x⌋.
• Sort within. Sort each bucket independently, typically with insertion sort because buckets are expected to hold ~1 element and insertion sort is unbeatable on tiny, nearly-sorted arrays.
• Gather. Concatenate the buckets in index order. Because bucket i holds only values less than every value in bucket i+1, the concatenation is globally sorted with no merge step.

The load-bearing invariant is a partition-order property: for buckets B₀, B₁, …, B_k-1, every key in Bᵢ is ≤ every key in B_i+1. Get the bucket-index function monotonic and this invariant makes the final gather a pure copy — the reason there is no O(n log k) merge like in merge sort. Bucket sort trades the merge for a hash-like address computation.

The algorithm, step by step

For the canonical case — n keys drawn from [0, 1) — the reference formulation from CLRS (Cormen, Leiserson, Rivest, Stein, §8.4) is:

BUCKET-SORT(A, n):
  let B[0..n-1] be an array of empty lists
  for i = 0 to n-1:
      idx = floor(n * A[i])      // map key to bucket
      B[idx].append(A[i])        // scatter
  for j = 0 to n-1:
      INSERTION-SORT(B[j])       // sort each bucket
  concatenate B[0], B[1], ..., B[n-1] in order   // gather

Three details decide whether this works:

• The index map must be monotonic and in-range. ⌊n·x⌋ works for x ∈ [0, 1). For a general range [lo, hi), rescale: idx = ⌊n·(x − lo)/(hi − lo)⌋, and clamp the boundary case x = hi to bucket n−1 (floating-point rounding can otherwise produce index n and an out-of-bounds write — a classic off-by-one).
• Bucket count k. Choosing k = n gives an expected load of exactly 1 element per bucket. Fewer buckets means bigger per-bucket sorts; more buckets means more empty-bucket overhead in the gather. k = n is the sweet spot for uniform data.
• Stability. Bucket sort is stable iff you append in input order (preserving order on scatter) and the inner sort is stable. Insertion sort is stable, so the standard formulation preserves the relative order of equal keys.

Why it runs in Θ(n): the average-case derivation

The scatter loop is Θ(n) and the gather loop is Θ(n) regardless of input. All the risk lives in the inner sorts. Let nᵢ be the number of keys that land in bucket i. Insertion sort on nᵢ elements costs O(nᵢ²), so the total inner cost is Σᵢ O(nᵢ²). The whole analysis reduces to bounding the expected value of Σ nᵢ².

Under the assumption that keys are independent and uniformly distributed, each nᵢ is Binomial(n, 1/n). A standard identity gives E[nᵢ²] = Var(nᵢ) + (E[nᵢ])². Here E[nᵢ] = n·(1/n) = 1 and Var(nᵢ) = n·(1/n)·(1 − 1/n) = 1 − 1/n. So:

• E[nᵢ²] = (1 − 1/n) + 1² = 2 − 1/n.
• Summing over all n buckets: E[Σ nᵢ²] = n·(2 − 1/n) = 2n − 1 = Θ(n).

Therefore total expected time is Θ(n) + Θ(E[Σ nᵢ²]) = Θ(n). The key surprise is that even though a single overloaded bucket costs O(nᵢ²), the expected squared bucket load stays constant per bucket because uniform keys spread out. This is the same balls-in-bins concentration that underpins the O(1) expected chain length in hash chaining — bucket sort is essentially a one-shot hash table where the buckets are numerically ordered.

Worst case: if the distribution assumption fails and all n keys map to one bucket, Σ nᵢ² = n² and you pay Θ(n²). Swap insertion sort for an O(m log m) sort inside each bucket and the worst case improves to Θ(n log n) — a common hardening that caps the downside at comparison-sort speed while keeping Θ(n) average behavior.

Space, stability, and the constant factors that matter

Space is Θ(n + k): the buckets themselves hold n elements total, plus k bucket headers. This is decidedly not in-place — bucket sort trades memory for the linear time, and with linked-list buckets you also pay allocator overhead and cache-unfriendly pointer chasing. High-performance implementations avoid linked lists entirely with a two-pass counting layout:

• Pass 1: compute each element's bucket index and histogram the counts (nᵢ).
• Prefix-sum the counts into bucket start offsets (a prefix sum — the same trick counting sort and LSD radix sort use to place elements in O(1)).
• Pass 2: scatter each element into a single contiguous output array at its bucket's running offset, then sort each contiguous bucket slice in place.

This contiguous variant keeps everything in one flat array, is far kinder to the cache, and is what most production distribution sorts actually do. The abstract "array of lists" is a teaching model, not a shipping design.

Constant-factor caveats: bucket sort touches memory twice (scatter + gather) and often randomly, so its Θ(n) can lose to an in-cache Θ(n log n) quicksort at small n. The crossover where distribution sorts win is typically large n with a genuinely uniform, wide key range. Below a few thousand elements, insertion sort or an introsort usually wins outright on real hardware because of branch prediction and cache locality.

Where it wins, and where it lives in real systems

Bucket sort is the right tool when three conditions hold together: (1) keys come from a known, bounded range; (2) they are roughly uniformly spread over it; and (3) n is large enough that the Θ(n) vs Θ(n log n) gap dominates the constant-factor penalty. Concrete niches:

• Sorting floating-point measurements — sensor readings, normalized scores, probabilities in [0, 1), geographic coordinates within a tile — where the physical process gives near-uniform values.
• The base pass of MSD radix sort. Radix sort is bucket sort applied one digit at a time: each digit-pass buckets by 2^b possible digit values. Every practical radix sort is a stack of bucket sorts, which is why the two are so often confused.
• Parallel and external (out-of-core) sorting. Buckets are independent, so scatter-then-sort-locally is embarrassingly parallel. Big-data frameworks lean on this: the shuffle phase of MapReduce and range-partitioners in Spark are bucket sort at cluster scale — partition keys into range buckets, sort each partition on its own node, concatenate. TeraSort, the canonical benchmark, is a distributed bucket sort with a sampled range partitioner.
• Spatial data structures. Spatial hashing for broad-phase collision detection buckets objects into a uniform grid — the same scatter-by-address idea, without the final gather.

The anti-pattern: sorting arbitrary comparable objects with unknown distribution. There, you cannot form a monotonic index map, and a general-purpose introsort or Timsort is the correct default.

Pitfalls, edge cases, and variants

Skewed input is the silent killer. The moment your data clusters — log timestamps bunched near business hours, prices piled at round numbers, Zipf-distributed frequencies — one or two buckets absorb most keys and you slide toward Θ(n²). Mitigations, in increasing order of robustness:

• Sample the data and choose non-uniform bucket boundaries (equal-count quantiles instead of equal-width bins). This is exactly what Spark's RangePartitioner and TeraSort's sampler do — reservoir-sample the keys, pick split points at the sample quantiles, and the buckets end up balanced even for skewed distributions.
• Harden the inner sort. Use an O(m log m) sort (or recurse with bucket sort) so the worst case is Θ(n log n), not Θ(n²).
• Recursive / adaptive bucketing. If a bucket is still large, bucket-sort it again on a finer sub-range.

Other edge cases:

• The boundary value. With map ⌊n·x⌋, an x equal to the range maximum indexes to n (out of bounds). Always clamp: idx = min(idx, k−1).
• Duplicates and equal keys. All identical keys pile into one bucket — a degenerate O(n²) case that a hardened inner sort or a fast-path "all-equal bucket" check should handle.
• Negative numbers and non-uniform types. The index map must be a correct monotonic rescale of the actual [min, max] range; forgetting to shift by the minimum silently sends negatives to bucket 0.
• Not comparison-free at heart. Bucket sort still compares inside each bucket — it just does very few comparisons. It is "non-comparison" only in that the top-level partition uses arithmetic, not comparisons, which is what lets it beat the Ω(n log n) bound.

Related variants: Proxmap sort and histogram sort are essentially the counting-layout bucket sort above; flashsort is a well-known in-place, single-array bucket sort that classifies into m ≈ 0.1n buckets and permutes in place for near-Θ(n) time with O(1) extra space.

Bucket sort against the linear-time and comparison-sort alternatives

Algorithm	Avg time	Worst time	Extra space	Assumption
Bucket sort	Θ(n)	Θ(n²)	Θ(n + k)	Keys ~ uniform over a known range
Counting sort	Θ(n + k)	Θ(n + k)	Θ(k)	Small integer key range k
Radix sort (LSD)	Θ(d·(n + b))	Θ(d·(n + b))	Θ(n + b)	Fixed-width d-digit keys
Quicksort	Θ(n log n)	Θ(n²)	Θ(log n)	None (comparison only)
Merge sort	Θ(n log n)	Θ(n log n)	Θ(n)	None (comparison only)