The amount of memory required for bucketing in problem 4.36 can be reduced when the elements to be sorted are binary strings in the interval [0, 2" - 1] for some b. The algorithm consists of b...

The amount of memory required for bucketing in problem 4.36 can be reduced when the elements to be sorted are binary strings in the interval [0, 2" - 1] for some b. The algorithm consists of b iterations. During iteration i, i = 0, 1, .. , b-1, - each element to be sorted is placed in one of two buckets depending on whether its ith bit is 0 or 1; the sequence is then reconstructed using procedure ALLSUMS so that all elements with a 0 ith bit precede all the elements with a 1 ith bit. Show that in this case sorting can be completed in 0(b log n) time using 0(n) processors and 0(n) memory locations.