Bucket Sort — Mathematical Foundations and Complexity Theory¶

Definition (Bucket Sort): given an input array A = [a_1, ..., a_n] drawn from
a totally ordered set (U, <=), a number of buckets k in N+, and a mapping
function f : U -> {0, 1, ..., k-1}, Bucket Sort produces an array A' which
is a permutation of A satisfying A'[i] <= A'[j] for i < j.

The algorithm is:

  1. Initialize k empty lists B_0, ..., B_{k-1}.
  2. For each a in A: append a to B_{f(a)}.                       (Scatter)
  3. For each B_i: sort B_i in place using inner sort S.          (Inner sort)
  4. Output the concatenation B_0 || B_1 || ... || B_{k-1}.       (Gather)

Correctness precondition (monotonicity of f):
  For all x, y in U: x <= y  =>  f(x) <= f(y).

Stability: Bucket Sort is stable iff S is stable.

Theorem 1. The output A' of Bucket Sort is a sorted permutation of A.

Proof.

Permutation: every input element a is appended to exactly one bucket B_{f(a)}
in the scatter phase. The inner sort permutes within a bucket. The gather
phase concatenates all buckets. Each a appears in the output exactly once. QED

Sortedness:

Invariant I_scatter (after scatter step on a_i):
  For every j < i, a_j lies in some B_{f(a_j)}. Across all buckets, no element
  has been lost or duplicated.

Invariant I_inner (after sorting B_i, for any i):
  B_i is sorted ascending: B_i[p] <= B_i[q] for p < q.

Cross-bucket lemma:
  For all p < q in {0, ..., k-1}, for all x in B_p and y in B_q: x <= y.

Proof of cross-bucket lemma: by construction, x was scattered to B_p so
f(x) = p; y was scattered to B_q so f(y) = q. By monotonicity of f, if x > y
then f(x) >= f(y), i.e. p >= q, contradicting p < q. Hence x <= y. QED

Conclusion: Inner sort gives within-bucket order; cross-bucket lemma gives
between-bucket order; concatenation preserves both. Therefore the output is
sorted. QED

Theorem 2 (CLRS 8.4). If A is drawn i.i.d. uniformly from [0, 1) and
k = n with f(x) = floor(n * x), then E[T(n)] = Theta(n) for Bucket Sort
using Insertion Sort as the inner sort.

Proof. Let n_i denote the number of elements placed in B_i. The total runtime is:

  T(n) = Theta(n)           (scatter)
       + sum_{i=0}^{n-1} O(n_i^2)   (Insertion Sort per bucket)
       + Theta(n)           (gather)

So:

  E[T(n)] = Theta(n) + sum_{i=0}^{n-1} E[O(n_i^2)]
         = Theta(n) + n * E[n_0^2]                  (by symmetry).

Compute E[n_0^2]. Each of n elements independently lands in bucket 0 with
probability 1/n. So n_0 follows a Binomial(n, 1/n) distribution.

  E[n_0]    = n * 1/n         = 1.
  Var(n_0)  = n * 1/n * (1 - 1/n) = 1 - 1/n.
  E[n_0^2]  = Var(n_0) + (E[n_0])^2 = (1 - 1/n) + 1 = 2 - 1/n.

Therefore:

  E[T(n)] = Theta(n) + n * (2 - 1/n) = Theta(n). QED

Theorem 3. For any choice of mapping function f and bucket count k, an
adversary can construct an input of size n on which Bucket Sort runs in
Theta(n^2) time.

Proof sketch. Choose any j in {0, ..., k-1} and construct A with n elements
all satisfying f(a) = j. The scatter places all n elements into B_j. The
inner sort (Insertion Sort) runs in Theta(n^2). QED

If the inner sort is replaced by a comparison sort running in O(n log n)
worst case (e.g., TimSort, Merge Sort, Heap Sort), the worst-case runtime
of Bucket Sort becomes O(n log n) — but at the cost of the algorithm being
no faster than a plain comparison sort in this case.

Theorem 4. The work-span profile of Bucket Sort using a parallel inner sort:

  Work:   W(n) = O(n) + sum_i O(n_i log n_i) + O(n)
  Span:   S(n) = O(log n) (scatter via parallel prefix-sum)
              + O(log^2 n) (parallel inner sort per bucket, bitonic style)
              + O(log n) (parallel gather)
        = O(log^2 n)

  Parallelism: P(n) = W(n) / S(n).

1. Each thread t processes its slice of A and produces a local histogram
   H_t[i] = count of elements landing in bucket i.        Work O(n/p), span O(n/p).
2. Compute prefix sums of H_t across threads.             Work O(k * p), span O(log p).
3. Each thread writes its elements to global positions
   given by the prefix sum.                                Work O(n/p), span O(n/p).

Parameters: N = total input size, M = RAM size, B = block size.

External Bucket Sort (one pass over input, k = floor(M/B) buckets):

  Scatter:  N/B reads, N/B writes (each block read once, written to its bucket).
  Sort:     N/B reads, N/B writes (sort each bucket in RAM, write back).
  Gather:   N/B reads, N/B writes (concatenate).
  Total I/O: O(N/B), with constant ~6.

External Merge Sort (run generation + log_k(N/M) merge passes):

  Total I/O: O((N/B) * log_{M/B}(N/M)), with constant 2 per pass.

Theorem 5 (comparison sort lower bound). Any sorting algorithm that only
compares pairs of input elements must perform Omega(n log n) comparisons
in the worst case.

Proof sketch: a comparison sort corresponds to a binary decision tree whose
leaves are the n! possible permutations. A binary tree with n! leaves has
height at least ceil(log_2 n!) = Theta(n log n). QED

Theorem 6. Bucket Sort is NOT a comparison sort and is therefore not
subject to the Omega(n log n) lower bound.

Proof. The scatter phase uses arithmetic (the value of f(a)) rather than
comparisons. Bucket Sort can run in expected O(n) (Theorem 2), strictly
beating the comparison-sort lower bound. QED

Claim: For inputs drawn i.i.d. from a known continuous distribution F with
bounded density, Bucket Sort with f(x) = floor(k * F(x)) and k = Theta(n)
runs in expected Theta(n) time.

Proof: bucket sizes follow Multinomial(n; p_0, ..., p_{k-1}) with p_i = 1/k.
Same calculation as Theorem 2 gives E[T(n)] = Theta(n). QED

Implication: when the CDF F is known (e.g., uniform, exponential, normal),
Bucket Sort is provably optimal: no algorithm beats Theta(n) for sorting n
elements.