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[A[i]nr]. We may use diferentially sized buckets for non-uniform distributions.

Complexity

This takes Θ(n) on average (small buckets).