18) We'll restrict sorting so that in array of length N, elements are
    integers of range 0..2*N-1. Now write a O(log N) time O(N) work
    sorting algorithm. Hint: blocking and bucketsort.

procedure sort18(A : array[0..N-1] of 0..2*N-1);
	var B, P : array[0..2*N-1] of 0..1;

	for i := 0 to 2*N-1 pardo	# 2logN time with N/logN processors
		B[i] := 0;

	for i := 0 to N-1 pardo		# logN time with N/logN processors
		B[A[i] := 1;

	blocking_0prefix_sum(B, P);	# 2logN time

	for i := 0 to 2*N-1 pardo       # 2logN time with N/logN processors
		if B[i]=1 then
			A[P[i]] := i;

procedure blocking_0prefix_sum(in A, out P : array[0..N-1]);

	block := N/P;
	for i := 0 to P-1 pardo
		start := i*block;
		end   := (i+1)*block-1;
		P[start] := 0;
		s := A[start];
		for j := start+1 to end do
			P[j] := s;
			s := s + A[j];
		PP[i+1] := s;
	0prefix-sum(PP);
	for i := 0 to P-1 pardo
		for j := start to end do
			P[j] := P[j] + PP[i];