# Uniform Bucket Sort

# 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

```text id="p2x9rm"
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)

```python id="n4q7zb"
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
```