Bucket Sort for Uniform Samples

Worked Solution

How to Think About It: Bucket sort exploits the fact that when inputs are uniformly distributed, you can predict roughly where each element belongs. If you divide $[0, 1)$ into $n$ equal-width buckets, a uniform draw lands in bucket $\lfloor n \cdot x \rfloor$, and on average each bucket gets about one element. Sorting tiny buckets is nearly free, so the total work is dominated by the $O(n)$ cost of distributing elements -- not by comparison sorting.

Algorithm:

Create $n$ empty buckets indexed $0, 1, \ldots, n-1$. For each sample $x_i$, place it in bucket $\lfloor n \cdot x_i \rfloor$. Then sort each bucket individually using insertion sort. Finally, concatenate the sorted buckets in order.

Why insertion sort? Each bucket has $O(1)$ elements in expectation, and insertion sort is optimal for tiny lists (no recursion overhead, good cache behavior, $O(1)$ for a single element).

Pseudocode:

```python def bucket_sort(arr): n = len(arr) if n <= 1: return arr

# Create n empty buckets buckets = [[] for _ in range(n)]

# Distribute elements into buckets for x in arr: idx = int(n * x) # floor(n * x) # Guard against x == 1.0 edge case if idx == n: idx = n - 1 buckets[idx].append(x)

# Sort each bucket (insertion sort) for bucket in buckets: insertion_sort(bucket)

# Concatenate result = [] for bucket in buckets: result.extend(bucket) return result

def insertion_sort(lst): for i in range(1, len(lst)): key = lst[i] j = i - 1 while j >= 0 and lst[j] > key: lst[j + 1] = lst[j] j -= 1 lst[j + 1] = key ```

Proof of $O(n)$ Expected Time:

Let $n_j$ be the number of elements in bucket $j$. The total work is:

$$T(n) = O(n) + \sum_{j=0}^{n-1} O(n_j^2)$$

The first $O(n)$ term covers bucket creation and element distribution. The $O(n_j^2)$ term is the insertion sort cost for bucket $j$.

We need $E\left[\sum_{j=0}^{n-1} n_j^2\right]$. Each element lands in bucket $j$ independently with probability $1/n$, so $n_j \sim \text{Binomial}(n, 1/n)$. For a $\text{Binomial}(n, 1/n)$ random variable:

$$E[n_j^2] = \text{Var}(n_j) + (E[n_j])^2 = n \cdot \frac{1}{n} \cdot \left(1 - \frac{1}{n}\right) + 1 = 2 - \frac{1}{n}$$

Summing over all $n$ buckets:

$$E\left[\sum_{j=0}^{n-1} n_j^2\right] = n \cdot \left(2 - \frac{1}{n}\right) = 2n - 1 = O(n)$$

So the total expected running time is $O(n) + O(n) = O(n)$.

Space Analysis:

We allocate $n$ bucket lists (each initially empty) and store $n$ elements total across all buckets. The output array also has $n$ elements. Total extra space: $O(n)$.

Edge Cases and Performance Degradation:

• Non-uniform distribution (e.g., $\text{Beta}(5, 1)$ skewed toward 1): Most elements cluster in a few buckets near the high end, while low-end buckets stay empty. The heavily loaded buckets have $O(n)$ elements, and sorting them takes $O(n^2)$ -- the algorithm degrades to quadratic. Fix: use quantile-based bucket boundaries instead of equal-width. If you know (or estimate) the CDF $F$, assign element $x$ to bucket $\lfloor n \cdot F(x) \rfloor$. This re-uniformizes the distribution across buckets.

• Heavy-tailed distribution (e.g., Pareto, Cauchy): The support is unbounded, so fixed-width buckets on $[0,1)$ do not even cover the domain. Even if you extend the range, extreme values create a few buckets with massive counts. Fix: clip or transform the data first (e.g., apply the empirical CDF), or switch to a comparison-based sort like merge sort which guarantees $O(n \log n)$ worst case.

• Many duplicates (point masses): All duplicates land in the same bucket, creating a large bucket regardless of the overall distribution. Insertion sort still handles this in $O(k^2)$ for $k$ duplicates. Fix: use a three-way partition or counting approach within each bucket.

• Adversarial input: An adversary who knows the bucket structure can put all elements in one bucket, forcing $O(n^2)$. Bucket sort is not a good choice when you cannot trust the input distribution.

Answer: Bucket sort achieves $O(n)$ expected time and $O(n)$ space for uniform inputs by assigning element $x$ to bucket $\lfloor n \cdot x \rfloor$ and sorting each bucket with insertion sort. The key insight is that uniform distribution guarantees each bucket has $O(1)$ expected elements. Performance degrades to $O(n^2)$ for skewed or heavy-tailed distributions because bucket loads become unbalanced; the fix is to use CDF-based bucket boundaries or fall back to a comparison sort.