SortingAlgorithmaka bin sort

Bucket Sort

Distribute elements into buckets by value range, sort each bucket, and concatenate — linear on uniform data.

▶ VisualizePattern: HashingPractice (2)
Progress

Overview

Bucket sort assumes the keys are drawn roughly uniformly from a known range (classically reals in [0, 1)). It creates k ≈ n buckets, drops each element into the bucket for its sub-range, sorts each bucket with a simple sort (Insertion Sort), and concatenates. Under the uniformity assumption each bucket holds O(1) elements on average, giving expected O(n) time.

It is stable if the per-bucket sort is stable and elements are appended in input order, and it needs O(n + k) extra space. It generalizes Counting Sort (buckets hold one key each) and is related to Radix Sort (buckets by digit). Its worst case is O(n²) when all elements land in one bucket, so it is a poor choice for skewed or adversarial inputs.

non-comparisonO(n + k)stableuniform distributionfloats

Intuition

A mental model before the formal terms.

Sorting a stack of forms by surname: first toss each into one of 26 trays labelled A–Z, then sort each tray by hand (each is small), then stack the trays in order. If half the surnames start with "S", the S tray takes most of the work — that is the uniformity assumption failing.

How it works

  1. Choose the number of buckets k (typically n) and a mapping from value to bucket index, e.g. ⌊k · (x - min) / (max - min + ε)⌋.
  2. Scan the input and append each element to its bucket (preserving input order).
  3. Sort each bucket, usually with Insertion Sort since buckets are expected to be tiny (or recursively with bucket sort).
  4. Concatenate the buckets in index order.

Why it works

The mapping is monotonic: every element in bucket i is ≤ every element in bucket i + 1. So sorted buckets concatenated in order are globally sorted.

With n elements uniformly spread over n buckets, the expected sum of squared bucket sizes is O(n), so total insertion-sort work is expected O(n) (CLRS §8.4).

Recognition

How to tell a problem wants this.

  • Values are floats or reals uniformly distributed in a known interval.
  • The problem hints at "linear time" with values in a bounded range but too many distinct values for Counting Sort.
  • Maximum gap / "sort by frequency" problems where bucketing by a derived key avoids a full sort.
“have you seen this before” → Hashing

Interactive visualization

Play, step, change the input. ← → and space work too.

a
29
0
25
1
3
2
49
3
9
4
37
5
21
6
43
7
12
8
33
9
bucket 0 [3..12]
bucket 1 [13..21]
bucket 2 [22..31]
bucket 3 [32..40]
bucket 4 [41..49]
1/17Use k=5 buckets over the value range [3, 49]. Bucket sort works best when values are spread roughly uniformly, so each bucket gets few elements.
Element being placedBucket receiving itSorted
PseudocodeLearn Bucket Sort →
1k = number of buckets; lo = min(a); hi = max(a)
2for x in a:
3  b = floor((x - lo) / (hi - lo + 1) * k)
4  buckets[b].append(x)
5for each bucket: insertionSort(bucket)
6a = concat(buckets)
Variables
k5
lo3
hi49
Complexity
best O(n + k)
avg O(n + k)
worst O(n²)
space O(n + k)
Speed

Pseudocode

1k = n; buckets = [[] for _ in range(k)]
2for x in a: buckets[floor(k * (x - mn) / (mx - mn + eps))].append(x)
3for each bucket: insertionSort(bucket)
4return concat(buckets)

Implementations

1def bucket_sort(a: list[float]) -> list[float]:
21 · Handle trivial input and find the value range
3    n = len(a)
4    if n <= 1:
5        return a[:]
6    mn, mx = min(a), max(a)
7    if mn == mx:
8        return a[:]
92 · Distribute elements into n buckets by sub-range
10    buckets: list[list[float]] = [[] for _ in range(n)]
11    width = (mx - mn) / n
12    for x in a:
13        idx = min(n - 1, int((x - mn) / width))
14        buckets[idx].append(x)
153 · Insertion-sort each bucket (stable)
16    for b in buckets:
17        for i in range(1, len(b)):
18            key = b[i]
19            j = i - 1
20            while j >= 0 and b[j] > key:
21                b[j + 1] = b[j]
22                j -= 1
23            b[j + 1] = key
244 · Concatenate buckets in index order
25    out: list[float] = []
26    for b in buckets:
27        out.extend(b)
28    return out
Walkthrough
  1. The guards return a[:] (a shallow copy) so callers never receive the input list aliased.
  2. [[] for _ in range(n)] builds n independent lists; [[]] * n would alias one list n times.
  3. int((x - mn) / width) truncates toward zero (safe here because the offset is non-negative), and min(n - 1, ...) clamps mx into the last bucket.
  4. The explicit insertion sort keeps the example self-contained and stable; the strict > never moves equal values past each other.
  5. out.extend(b) appends each bucket in O(len(b)) without building intermediate lists.
Complexity (this implementation)
time O(n + k) expected on uniform data, O(n²) worst · space O(n + k)

In real Python, sorted(b) per bucket (TimSort, in C) beats the pure-Python insertion sort even for small buckets.

Language notes
  • sorted(b) is stable TimSort, so replacing the inner sort with it keeps the whole algorithm stable — and it is the idiomatic choice.
  • The classic formulation for uniform floats in [0, 1) reduces the index to int(x * n) — no min/max scan needed.
  • Honest caveat: sorted(a) on the whole list runs in C at O(n log n) and usually beats this expected-O(n) pure-Python loop; in Python, bucket sort mostly pays off as a bucketing *pattern* (frequency buckets, maximum gap).
Common mistakes in this language
  • Building buckets with [[]] * n — every slot is the same list.
  • Expecting int() to floor: int(-0.5) is 0 while math.floor(-0.5) is -1. Values here are non-negative, but the pattern bites when bucketing signed offsets.
  • Skipping the mn == mx guard — ZeroDivisionError.
Language differences that matter here
  • Bucket creation: C++ std::vector<std::vector<double>>(n) and Python [[] for _ in range(n)] create independent buckets; in JS/TS new Array(n).fill([]) shares ONE array — use Array.from({ length: n }, () => []).
  • Inner sort: Python sorted(b) is stable TimSort in C (the idiomatic choice); JS b.sort() needs the (x, y) => x - y comparator or numbers sort lexicographically; C++ std::sort is unstable introsort — use std::stable_sort or insertion sort if stability matters.
  • Truncation: Python int() and C++ static_cast truncate toward zero, Math.floor in JS/TS floors — identical for the non-negative offsets used here, different for signed keys.
  • Numbers: JS/TS have only doubles, so floats are the natural input; C++ picks the element type explicitly; Python floats are doubles but each list element is a boxed object.

Complexity

Best
O(n + k)
Average
O(n + k)
Worst
O(n²)
Space
O(n + k)

Average assumes uniformly distributed keys and k ≈ n buckets. Worst case: all keys in one bucket with an O(n²) inner sort. Stable if the inner sort is stable.

Compare growth rates in the Complexity Explorer →

When to use — and when not to

Use it when
  • Uniformly distributed floats in a known range (e.g. random numbers in [0, 1), normalized scores).
  • When a cheap monotone hash spreads keys evenly and you want expected linear time.
  • Problems that only need elements grouped by coarse range (maximum gap, frequency buckets).
Avoid it when
  • Skewed, clustered, or adversarial data — buckets become unbalanced and the sort degrades to O(n²).
  • Unknown value range (you must scan for min/max or guess bucket boundaries).
  • Memory is limited — buckets need O(n + k) extra space.

Alternatives

Counting SortRadix SortQuick SortMerge Sort

Common mistakes

  • Off-by-one mapping the maximum value to bucket k (out of range) — clamp to k - 1 or add an epsilon to the divisor.
  • Using Quick Sort inside buckets; it is overkill and unstable — insertion sort is the right inner sort.
  • Choosing too few buckets (k ≪ n), which makes the inner sorts dominate.
  • Assuming linear time without checking the distribution.

Interview patterns

  • Maximum gap: n - 1 buckets of width (max - min)/(n - 1) guarantee the answer is between buckets, not within one.
  • Top-k frequent elements: bucket elements by frequency (index = count) then read from the high end.
  • Sort characters by frequency via frequency buckets.
  • Contains duplicate III: buckets of width t + 1 to find values within t in O(n).
Interview questions on this
Mock interviews

Example problems

Group AnagramsmediumTop K Frequent Elementsmedium