Uniform Bucket Sort

Uniform bucket sort is a specialization of bucket sort where elements are assumed to be uniformly distributed over a known interval. Buckets are defined with equal width, and a direct arithmetic mapping assigns each element to a bucket.

The design goal is to keep bucket sizes balanced so that each bucket remains small and can be sorted quickly.

Problem

Given an array $A$ of $n$ values drawn from a range $[a, b)$ with approximately uniform distribution, sort the array.

Idea

Divide the interval $[a, b)$ into $k$ equal segments:

$$ [a, b) = \bigcup_{i=0}^{k-1} [a + i\Delta, a + (i+1)\Delta) $$

where:

$$ \Delta = \frac{b - a}{k} $$

Each element is mapped to a bucket using:

$$ i = \left\lfloor \frac{x - a}{\Delta} \right\rfloor $$

Then:

1. distribute elements into buckets
2. sort each bucket
3. concatenate results

Algorithm

uniform_bucket_sort(A, a, b, k):
    buckets = [empty list for _ in range(k)]
    delta = (b - a) / k

    for x in A:
        i = floor((x - a) / delta)
        if i == k:
            i = k - 1
        buckets[i].append(x)

    for i from 0 to k - 1:
        sort(buckets[i])

    return concatenate(buckets)

Example

Sort:

$$ A = [12, 45, 23, 51, 37, 29, 18] $$

Range:

$$ [10, 60),\ k = 5,\ \Delta = 10 $$

Buckets:

bucket	range	elements
0	[10, 20)	12, 18
1	[20, 30)	23, 29
2	[30, 40)	37
3	[40, 50)	45
4	[50, 60)	51

Sorted buckets:

$$ [12, 18],\ [23, 29],\ [37],\ [45],\ [51] $$

Concatenate:

$$ [12, 18, 23, 29, 37, 45, 51] $$

Correctness

The bucket mapping ensures that all elements in bucket $i$ are less than or equal to all elements in bucket $i+1$. Sorting each bucket yields local order, and concatenation yields global order.

Complexity

Let:

• $n$ be number of elements
• $k$ be number of buckets

Expected time:

$$ O(n + k) $$

assuming uniform distribution so each bucket has size about $n/k$.

Worst case:

$$ O(n^2) $$

if all elements fall into a single bucket.

Space:

$$ O(n + k) $$

Properties

property	value
stable	depends on inner sort
in place	no
distribution assumption	uniform
sensitivity	high to skew

When to Use

Use uniform bucket sort when:

• values are approximately uniformly distributed
• range is known and bounded
• fast average case is preferred
• simple mapping is sufficient

Avoid when distribution is skewed or unknown, since bucket imbalance degrades performance.

Implementation (Python)

def uniform_bucket_sort(a, a_min, a_max, k):
    buckets = [[] for _ in range(k)]
    delta = (a_max - a_min) / k

    for x in a:
        i = int((x - a_min) / delta)
        if i == k:
            i = k - 1
        buckets[i].append(x)

    result = []
    for b in buckets:
        result.extend(sorted(b))

    return result