# 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 $\left[0,r\right)$ by using $B\left[⌊\frac{A\left[i\right]\cdot n}{r}⌋\right]$. We may use diferentially sized buckets for non-uniform distributions.

## Complexity

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