Bucket sort assumes that the input is drawn from a uniform distribution and has an average-case running time of O(n).
We assume that the input is generated by a random process that distributes elements uniformly and independently over the interval [0,1).
Bucket sort divides the interval [0,1) into n equal-sized subintervals, or buckets, and then distributes the n input number into the buckets. Since the inputs are uniformly and independently distributed over [0,1), we do not expect many numbers to fall into each bucket.
To produce the output, we simply sort the numbers in each bucket and then go through the buckets in order, listing the elements in each.
Our code assumes that the input is an n-element array A, and that each element x in the array satisfies that 0 <= x < 1. The code requires an auxiliary array B[0..n-1] of linked lists (buckets) and assumes that there is a mechanism for maintaining such lists.
BUCKET-SORT(A):
let B[0..n-1] be a new array
n = A.length
for i = 0 to n-1
make B[i] an empty list
for i = 0 to n-1
insert A[i] into list B[|n*A[i]|]
for i = 0 to n-1
sort list B[i] with insertion sort
concatenate lists B[0],...,B[n-1] together in order