# Bucket Sort

## Algorithm

for i = 0 to n-1 do B[i] = 0
for i = 1 to n do put A[i] into B[floor(A[i]*n)]
for i = 0 to n-1 do quadratic-sort(B[i])
concat-buckets(B)

This may be modified for ranges $[0,r)$ by using $B[\lfloor \frac{A\left[i\right]\cdot n}{r}\rfloor ]$. We may use diferentially sized buckets for non-uniform distributions.

## Complexity

This takes $\Theta \left(n\right)$ on average (small buckets).