Bucket Sort
Imagine sorting a million floating-point numbers, each drawn independently and uniformly from `[0, 1)`. A comparison-based sort like Merge Sort or Quicksort guarantees `Θ(n log n)` time no matter what. This is because it must extract `log(n!) ≈ n log n` bits of information through pairwise comparisons alone. But if you already know something about the distribution of the input, things change. Not just that it's a sequence of numbers, but that it's spread roughly evenly over an interval. Then you can sidestep the comparison bottleneck entirely. You can sort in expected linear time. Bucket sort is the canonical example of an algorithm that buys speed by assuming structure in the input. The idea is disarmingly simple: split the range of possible values into equally sized intervals ("buckets"). Scatter each element into the bucket matching its value. Then sort each bucket's small contents (typically with Insertion Sort) and concatenate. When the input is uniformly distributed, each bucket ends up with only a constant number of elements on average. So the total work collapses from `n log n` to `Θ(n)`. This is not a magic trick that beats the Comparison-Sort Lower Bound. It respects it completely. The lower bound applies to algorithms that treat elements as opaque, comparable objects. Such algorithms receive no other information. Bucket sort works differently: it uses the numeric value of each key to compute a bucket index directly. This is an operation the comparison model doesn't allow. This is the same escape hatch used by Counting Sort and Radix Sort. Bucket sort is best understood as their continuous-valued cousin. This article builds bucket sort from first principles. It covers the placement rule and the pseudocode. It includes a full correctness and expected-time analysis, including why uniformity is the load-bearing assumption. It also offers a worked trace on a real array. Finally, it covers the traps that turn an elegant `Θ(n)` algorithm into an accidental `Θ(n²)` one.
- Bucket sort partitions the input range into `n` equal-width buckets, drops each element into its bucket by value, sorts each bucket locally, then concatenates.
- Expected running time is `Θ(n)` when input is drawn i.i.d. from a distribution close to uniform over a known range.
- Worst-case time is `Θ(n²)` — all elements landing in one bucket degrades to plain insertion sort on the whole array.
- It sidesteps the `Ω(n log n)` Comparison-Sort Lower Bound by using arithmetic on key values, not comparisons, to route elements — the same trick behind Counting Sort.
- Space is `Θ(n)` for the buckets themselves, on top of the input array.
- It's the right tool when you know the input is roughly uniform over a bounded range (hashing, histogramming, some numerical simulations) and the wrong tool when the distribution is skewed or unknown.
When input values are uniformly spread over a known range, mapping each value directly to a bucket index does the work that `Θ(n log n)` comparisons would otherwise have to do, yielding expected `Θ(n)` sorting.
The idea
Bucket sort assumes the `n` input keys lie in a known range, conventionally normalized to `[0, 1)`, and are drawn independently from a distribution that is (at least approximately) uniform over that range. The algorithm allocates `n` buckets, each responsible for a sub-interval of width `1/n`: bucket `i` owns `[i/n, (i+1)/n)`. Every key `x` is placed into bucket `⌊n·x⌋` by a single arithmetic computation — no comparisons against other keys are needed to decide which bucket it belongs in. Once all `n` keys have been distributed, each bucket is sorted independently, usually with Insertion Sort, because under the uniformity assumption each bucket is expected to hold only `Θ(1)` elements, and insertion sort is fast on tiny, nearly-empty lists despite being `Θ(k²)` in the worst case for a bucket of size `k`. Finally, the buckets are visited in order `0, 1, …, n−1` and concatenated; because bucket `i`'s interval lies entirely below bucket `i+1`'s interval, this concatenation produces a globally sorted array without any further comparisons across buckets. The key structural insight is a two-level decomposition of the sorting problem: a coarse, comparison-free partition step (bucket index = a hash-like function of the value) followed by a fine, comparison-based repair step within each small bucket. This mirrors the design of Counting Sort, which also partitions by value rather than comparison, but bucket sort generalizes it to continuous or large-range keys by grouping many values into shared intervals instead of giving every distinct key its own slot.
How it works
The algorithm has four phases: initialize the buckets, scatter elements into buckets by computed index, sort each bucket locally, and gather buckets back into one array in order.
Phase 1 — Initialize. Create `n` empty lists (or dynamic arrays), `B[0..n-1]`.
Phase 2 — Scatter. For each key `x` in the input (assumed to lie in `[0, 1)`), compute `i = ⌊n·x⌋` and append `x` to `B[i]`. This is a single arithmetic operation per element — `Θ(1)` work, `Θ(n)` total.
Phase 3 — Sort. Sort each bucket `B[i]` independently, typically with insertion sort since buckets are expected to be small.
Phase 4 — Gather. Concatenate `B[0], B[1], …, B[n-1]` in order to produce the final sorted array. ```text BUCKET-SORT(A, n) // A[0..n-1] are keys in the half-open interval [0, 1) let B[0..n-1] be new empty lists // Phase 2: scatter for j = 0 to n - 1 i = floor(n * A[j]) // bucket index, 0 <= i <= n-1 by construction insert A[j] into B[i] // Phase 3: sort each bucket locally for i = 0 to n - 1 INSERTION-SORT(B[i]) // Phase 4: gather buckets in order result = empty list for i = 0 to n - 1 append all elements of B[i] to result return result ``` ```text INSERTION-SORT(L) for j = 2 to length(L) key = L[j] i = j - 1 while i > 0 and L[i] > key L[i + 1] = L[i] i = i - 1 L[i + 1] = key ``` Two implementation details matter in practice. First, `i = ⌊n·x⌋` can equal `n` only if `x = 1` exactly; since the domain is the half-open `[0,1)`, this is excluded by assumption, but defensive code should clamp `i` to `n − 1` to guard against floating-point edge cases (e.g., `x` computed as `0.999999999999` that rounds up). Second, if the input range is `[a, b)` instead of `[0, 1)`, rescale first: `x' = (x − a) / (b − a)`, then bucket by `x'`.
Complexity & correctness
Correctness. The proof rests on a simple interval-monotonicity invariant: bucket `i` is assigned exactly the sub-interval `[i/n, (i+1)/n)`, and these intervals are pairwise disjoint and increasing in `i`. Every key `x` satisfies `x ∈ [⌊n·x⌋ / n, (⌊n·x⌋ + 1)/n)` by the definition of floor, so it is placed in exactly one bucket, and that bucket's interval is uniquely determined by `x`'s value. Consequently, for any two keys `x < y`:
- if they land in different buckets `i < i'`, then `x`'s bucket interval lies entirely below `y`'s bucket interval, so `x < y` is guaranteed by bucket order alone, with no comparison needed;
- if they land in the same bucket, the local insertion sort correctly orders them relative to each other.
Since gathering visits buckets in increasing index order and each bucket is internally sorted, the concatenated result is a sorted permutation of the input — this is precisely a merge of pre-partitioned, already order-compatible runs, requiring no merge step at all because the partition itself guarantees inter-bucket order. Insertion sort's own correctness (loop invariant: `L[1..i]` is sorted after outer iteration `i`) is assumed from Insertion Sort and composed here as a subroutine.
Expected-time analysis. Let `n_i` be the number of elements landing in bucket `i`. The total work is: ``` Θ(n) (scatter + gather, always) + Σ_{i=0}^{n-1} Θ(n_i²) (insertion sort per bucket, worst case per bucket) ``` Under the uniformity assumption, each of the `n` keys independently falls into bucket `i` with probability `1/n`, so `n_i` follows a `Binomial(n, 1/n)` distribution. We need `E[n_i²]`. Using `Var(n_i) = E[n_i²] − (E[n_i])²`: ``` E[n_i] = n · (1/n) = 1 Var(n_i) = n · (1/n) · (1 − 1/n) = 1 − 1/n E[n_i²] = Var(n_i) + (E[n_i])² = (1 − 1/n) + 1 = 2 − 1/n ``` So `E[n_i²] < 2` for all `n ≥ 1`. By linearity of expectation over all `n` buckets: ``` E[total sorting work] = Σ_{i=0}^{n-1} Θ(E[n_i²]) = Σ_{i=0}^{n-1} Θ(2 − 1/n) = Θ(n) ``` Adding the `Θ(n)` scatter/gather cost, the expected total running time is Θ(n). This holds regardless of which specific uniform sample is drawn — it's an average over the randomness of the input, not an assumption that requires randomized pivoting (contrast with Quicksort, where the algorithm itself randomizes; here the input is assumed random).
Worst case. If every key falls into a single bucket (e.g., all values equal, or a distribution concentrated on a tiny sub-interval), that bucket has `n_i = n`, and insertion sort on it costs `Θ(n²)`. Worst-case time is Θ(n²) — no better than plain insertion sort on the whole array, and bucket sort inherits none of quicksort's average-case robustness to adversarial permutations because its guarantee depends on the values' distribution, which an adversary who controls the input can always break.
Space. `Θ(n)` auxiliary space for the `n` buckets and their contents (this can be reduced to `Θ(n)` in-place variants with more care, but the simple version duplicates the array).
Stability. Bucket sort is stable if the per-bucket sort is stable (insertion sort is) and elements are appended to buckets in input order, since equal keys land in the same bucket and keep their relative order through a stable local sort.
Honest tradeoff. Bucket sort's `Θ(n)` expectation is a statement about typical uniform inputs, not a worst-case guarantee, and it is not a comparison sort — it requires random-access arithmetic on numeric keys (or a rank/CDF estimate for non-uniform data), unlike merge sort or heapsort, which work for any totally ordered type via a comparator alone.
Worked example
Take `A = [0.78, 0.17, 0.39, 0.26, 0.72, 0.94, 0.21, 0.12]`, `n = 8`. Bucket width is `1/8 = 0.125`.
| Element `x` | `⌊8·x⌋` = bucket index | Bucket contents after scatter |
|---|---|---|
| 0.78 | ⌊6.24⌋ = 6 | B6 = [0.78] |
| 0.17 | ⌊1.36⌋ = 1 | B1 = [0.17] |
| 0.39 | ⌊3.12⌋ = 3 | B3 = [0.39] |
| 0.26 | ⌊2.08⌋ = 2 | B2 = [0.26] |
| 0.72 | ⌊5.76⌋ = 5 | B5 = [0.72] |
| 0.94 | ⌊7.52⌋ = 7 | B7 = [0.94] |
| 0.21 | ⌊1.68⌋ = 1 | B1 = [0.17, 0.21] |
| 0.12 | ⌊0.96⌋ = 0 | B0 = [0.12] |
Note a subtlety visible here: 0.72 and 0.94, though both in the "high" region, land in different buckets (B5 and B7 respectively), while 0.17 and 0.21 collide into the same bucket B1 despite being farther apart in absolute terms than the gap between some other pairs — bucket boundaries are rigid, evenly spaced cut points, not adaptive to local density. After the scatter phase, buckets stand as: ``` B0 = [0.12] B1 = [0.17, 0.21] B2 = [0.26] B3 = [0.39] B4 = [] B5 = [0.72] B6 = [0.78] B7 = [0.94] ``` Each bucket is already sorted or trivially size-1 or size-0 in this instance (insertion sort on `[0.17, 0.21]` leaves it unchanged since `0.17 < 0.21`). Gathering `B0` through `B7` in order yields: ``` [0.12, 0.17, 0.21, 0.26, 0.39, 0.72, 0.78, 0.94] ``` which is exactly the sorted array. Total work: 8 arithmetic bucket computations, one 2-element insertion sort (constant work), and a linear-time gather — matching the `Θ(n)` prediction for this near-uniform sample.
A skewed second case, to show the failure mode. Let `A' = [0.01, 0.02, 0.03, 0.04, 0.05, 0.06, 0.07, 0.08]`, `n = 8`. Every value is below `0.125`, so `⌊8·x⌋ = 0` for all eight elements — they all land in `B0`, and `B4` through `B7` (and `B1` through `B3`) are empty. Insertion sort then runs on the full 8-element bucket, costing `Θ(n²)` for this bucket alone, with no parallel work saved elsewhere. This is bucket sort's worst case realized: a distribution that is not uniform over the assumed range `[0,1)` (it's uniform only over `[0, 0.08)`) defeats the load-balancing that makes the algorithm fast.
Common pitfalls & traps
| Pitfall | Why it happens | Fix |
|---|---|---|
| Assuming uniformity without checking | Real data (timestamps, prices, scores) is often clustered or skewed, not uniform | Rescale into buckets based on the actual empirical range/quantiles, or fall back to a comparison sort when distribution is unknown |
| Off-by-one on the top boundary | `x = 1.0` (or the maximum value) gives `⌊n·1⌋ = n`, an out-of-range index | Clamp: `i = min(⌊n·x⌋, n − 1)`, or use a strictly-less-than upper bound in input validation |
| Using a slow per-bucket sort for large buckets | If uniformity assumption fails and a bucket grows large, insertion sort's `Θ(k²)` becomes the bottleneck | Use a comparison sort with `Θ(k log k)` worst case (e.g., Merge Sort) inside buckets when bucket sizes cannot be bounded in advance |
| Forgetting to rescale a non-`[0,1)` input range | Formula `⌊n·x⌋` silently misbehaves or throws for values outside `[0,1)` | Always normalize: `x' = (x − min) / (max − min)` before bucketing |
| Treating it as a general-purpose sort | It's not comparison-based; misapplied to arbitrary/non-numeric keys it either doesn't apply or requires a custom bucket function | Reserve bucket sort for numeric (or rank-mappable) keys with a known or estimable distribution |
Pioneers & history
Bucket sort's core idea — partitioning by value rather than comparing pairs — traces back to the same lineage as radix and counting methods used in mechanical card-sorting and tabulating machines of the early 20th century, well before formal complexity analysis existed. The technique was later placed on rigorous footing as part of the broader study of non-comparison sorting, which crystallized alongside the formalization of the `Ω(n log n)` Comparison-Sort Lower Bound in the mid-20th century: once theorists proved what comparisons alone cannot achieve, algorithms that legitimately use more information about keys — like bucket sort, counting sort, and radix sort — were understood as a distinct, complementary class rather than competitors violating some universal bound.
Origins · 1 minHarold H. Seward and how this was discovered
Where this matters
Bucket sort's scatter-then-locally-sort pattern shows up wherever data is numeric, roughly uniform, and speed matters more than worst-case robustness. Histogram construction in graphics, statistics, and databases is essentially bucket sort's scatter phase in isolation — binning continuous values into equal-width intervals is the same operation, just without the final local-sort step (or with it, if a sorted histogram bin is needed). Hash table bucket chaining is structurally identical to bucket sort's scatter phase: a hash function maps keys to buckets, and if the hash distributes keys uniformly, each chain stays short, exactly mirroring the `E[n_i] = 1` calculation used in bucket sort's analysis.
External sorting systems that sort data too large for memory sometimes use a bucket-sort-like first pass to partition records into range-bounded chunks (using known or estimated key distributions) that each fit in memory, then sort each chunk independently before writing it back — this is bucket sort at the scale of disk I/O rather than array indices. Radix sort, one of the most widely used sorting algorithms for fixed-width integers and strings (used in suffix array construction, GPU sorting libraries, and some database engines), can be viewed as repeated bucket sort by digit, cycling through digit positions from least to most significant. In scientific computing, bucket sort (or its close relatives) is used to sort particles or grid points by spatial coordinate in simulations where positions are naturally bounded and roughly uniformly distributed, feeding directly into spatial indexing structures used in collision detection and N-body simulations.
:::quiz[In the expected-time derivation, what is E[n_i²] for bucket i under Binomial(n, 1/n)?]
- Exactly 1 for all n
- n² / 4
- 2 − 1/n, which is bounded by a constant ✓
- log n
Ask the tutor: How would you adapt bucket sort's bucket-width formula if the input distribution is Gaussian rather than uniform?
Is bucket sort a comparison sort?
No. Bucket sort computes a bucket index directly from a key's numeric value via `⌊n·x⌋`, which is an arithmetic operation, not a comparison between two elements. Comparisons only occur within a bucket, during the local insertion sort, and even that is a small-scale, low-cost operation because buckets are expected to be tiny. Because the algorithm extracts information from key values beyond a total order (it uses actual magnitude, not just relative rank), it is exempt from the `Ω(n log n)` Comparison-Sort Lower Bound, which applies strictly to algorithms that access keys only through pairwise comparisons.
What happens if the input isn't actually uniformly distributed?
Performance degrades gracefully in mild cases and catastrophically in extreme ones. If the distribution is only mildly non-uniform, some buckets get a bit fuller than others but the total work stays close to linear. If the distribution is heavily skewed — for instance, most values clustered in a narrow sub-range — one or a few buckets absorb most of the elements, and their local insertion sorts cost `Θ(k²)` for bucket size `k`, potentially degrading the whole algorithm to `Θ(n²)`. In production, either verify the distribution empirically, use adaptive bucket boundaries based on quantiles, or fall back to a `Θ(n log n)` comparison sort for safety.
How is bucket sort different from counting sort?
Both are non-comparison sorts that route elements by value, but counting sort assigns one bucket per distinct key value (assuming a small, discrete key universe), while bucket sort assigns one bucket per interval of a continuous or large-range domain, holding potentially many distinct values per bucket. Counting sort's buckets need no internal sorting since all elements in a bucket are equal; bucket sort's buckets require a local sort since elements within a bucket can differ. Counting sort's complexity is `Θ(n + k)` for key universe size `k`; bucket sort's is expected `Θ(n)` regardless of the size of the continuous domain, provided uniformity holds.
Can bucket sort be made stable, and does it matter?
Yes — bucket sort is stable as long as elements are appended to their bucket in the order they appear in the input, and the local sort used within each bucket (like insertion sort) is itself stable. Stability matters whenever equal keys carry distinguishing secondary information that should preserve its original relative order, such as sorting transaction records by amount while keeping same-amount transactions in timestamp order. If a non-stable local sort (e.g., a naive in-place quicksort) is used instead, stability is lost even though the final numeric order is still correct.
Why is insertion sort the conventional choice for sorting within buckets rather than something asymptotically faster?
Under the uniformity assumption, the expected bucket size is `Θ(1)`, specifically `E[n_i] = 1` for `n` buckets and `n` elements. Insertion sort's cost on a list of size `k` is `Θ(k + k²)` in general, but for the expected constant-sized buckets that appear here, this constant-factor-friendly, low-overhead algorithm outperforms asymptotically superior but higher-constant-overhead algorithms like merge sort, which pay recursion and merge-buffer costs that aren't worthwhile for lists of average size close to 1. If bucket sizes cannot be bounded (uniformity is uncertain), switching to a `Θ(k log k)` worst-case sort inside buckets is the safer engineering choice.
How do you choose the number of buckets, and does it have to equal n?
Using `n` buckets for `n` elements is the standard choice because it makes the expected bucket load exactly `E[n_i] = 1`, which is what drives the `Θ(n)` expected-time result via the variance calculation. Using fewer buckets than `n` increases expected bucket size and pushes more work into the local sorts (trading bucket-management overhead for sort overhead), while using many more buckets than `n` wastes memory on buckets that stay empty without meaningfully reducing per-bucket work below a small constant. In practice, `n` buckets balances memory use and expected per-bucket cost cleanly, matching the theoretical analysis exactly.
Does bucket sort work for integers, or only for real numbers in [0,1)?
It works for any numeric domain with a known or estimable range, not just `[0,1)`; you simply rescale. For integers in `[0, M)`, choose `n` buckets each covering a sub-range of width `M/n`, and compute the bucket index as `⌊n·x / M⌋` instead of `⌊n·x⌋`. This is exactly how bucket sort generalizes to arbitrary bounded numeric ranges, and it's conceptually close to how radix sort partitions integers by digit value at each pass, though radix sort uses a fixed small number of buckets (e.g., 10 for decimal digits) applied repeatedly rather than one large bucketing pass.