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:

distribute elements into buckets
sort each bucket
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