Bucket Sort

Assume a_i is U [0, 1)

The idea is to divide [0. 1) into intervals or buckets of size 1/n. Then pass through an array A, putting numbers in the buckets. Uniformity assumptions means that each bucket will have only a few (maybe n) elements after the pass.

B[0 ... n-1] is an array of linked lists (to hold the undetermined number of elements.)

Bucket-Sort (A)

1. n ¬ length[A]

2. for i ¬ 1 to n

3.      do insert A[i] into list B[ën A[i]û]

4. for i ¬ 0 to n - 1

5.      do sort list B[i] with insertion sort

6. concatenate the lists B[0], B[1] ... B[n-1] together in order

Note that ën A[i]û ® 0. 1, ... , n-1 when 0 A[i] < 1. Also note that this is just a "hash sort" algorithm
with ën A[i]û as the hash function.

Does bucket sort work? A[i] A[j]

1. If they get put in the same bucket insertion sort does the right thing.

2. If they are put in different buckets. B[i'] B[j'] with i' < j' . Must have A[i] £ A[j], of mpt i' = ën A[i]û ³ ën A[j]û = j' and i ³ j' is a contradiction. So it must be that A[i] £  A[j].

Running time:

Everything except the little insertion sorts are O (n). Assume that B[i] has n_i elements, then the worst-case of insertion sort is O (n²). Expected time to sort is O ( E[n_i²]), and so all together:

n-1 å O ( E [ni2] ) =  O [  i = 0

n-1 å E [ni2]  ]  i = 0

What is :

i^th bucket is chosen with p_i = 1/n. Do this n times. n_i is a binomial with p = 1/n and n E [n_i] = n p = n 1/n = 1,  var [n_i] = n p ( 1-p ) = 1 - 1/n