X2) Implement one stage of the parallel radix sort algorithm described
    at lectures (and other side of this paper) for CREW PRAM. Write the
    algorithm in programming-language -like algorithm notation. The
    algorithm should work with any number of processors, but you should
    assume that P << N.

You need to write all parts of a stage: counting local occurrences,
prefix sums and assignment. You do not, however, need to implement the
whole sorting which repeats this sorting by one subkey m/r times. You
can refer to the r bits by subkey(key, r, 0), where key is the key
(e.g., A[i]), r is the constant radix (number of bits), e.g., 10, and 0
means which part of the whole key you refer (it suffices to have 0
only).


# grading
# self evaluation 1p
# counting occurences 1p
# prefix sum 2p
# actual sortig according to prefx 1p
# late (Wed 2pm to Thu 2pm : -1)
# total 5


procedure radix_part(in A, out B : array[0..N-1], P, r, part);

R := 2^r;
block := N/P;

var occ[0..R-1, 0..P-1] of integer;
    rowsums[0..R-1];

# reset table, O(R)
for i := 0 to P-1 pardo
	for j := 0 to R-1 do
		occ[j, i] := 0;

# count occurences to local part of A
# N/P
for i := 0 to P-1 pardo
	start := i*block;
	end   := (i+1)*block-1;
	for j := start to end do
		inc(occ[subkey(A[j], r, part), i], 1);

# count row prefixes
# O(R)
for i := 0 to R-1 pardo
	s := 0;
	for j := 0 to P-1 do
		t := occ[i, j];
		occ[i, j] := s;
		s := s + t;
	rowsums[i] := s;

# do prefix sum for rowsums
# O(R/P + logP)
blocking_0prefix-sum(rowsums);

# rewrite occ
for i := 0 to P-1 pardo
	for j := 1 to R-1 do
		occ[j, i] := occ[j, i] + rowsums[j-1];

# actual sorting accorind to occ
# N/P
for i := 0 to P-1 pardo
	start := i*block;
	end   := (i+1)*block-1;
	for j := start to end do
		B[occ[subkey(A[j], r, part), i]] := A[j];
		inc(occ[subkey(A[j], r, part), i], 1);
		
		
	
procedure blocking_0prefix_sum(in A, out R : array[0..N-1]);

	block := N/P;
	for i := 0 to P-1 pardo
		start := i*block;
		end   := (i+1)*block-1;
		R[start] := 0;
		s := A[start];
		for j := start+1 to end do
			R[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
			R[j] := R[j] + PP[i];