Bucket Sort

A bucket-sort does not use comparison. Let $S$ be a sequence of $n$ entries with keys in the range $[0,N-1]$.

Bucket-sort uses the keys as indices into an auxiliary array $B$ of sequences.

• Phase 1: empty sequence $S$ by moving each entry $(k,o)$ into its bucket $B[k]$
• Phase 2: for $i=0,\dots ,N-1$, move the entries of bucket $B[i]$ to the end of sequence $S$

Between the two phases, bucket sort takes $O(n+N)$ time:

• Phase 1 takes $O(n)$ time
• Phase 2 takes $O(N)$ time