Consider the enumeration sort algorithm presented in Section 9.6.1 . Show how the algorithm can be implemented on each of the following:

a: a CREW PRAM b: a EREW PRAM c: a hypercube-connected parallel computer d: a mesh-connected parallel computer.

Analyze the performance of your formulations. Furthermore, show how you can extend this enumeration sort to a hypercube to sort n elements using p processes.

algorithm presented in Section 9.6.1

1. procedure ENUM SORT (n) 2. begin 3. for each process P1,j do 4. C[j] :=0; 5. for each process Pi,j do 6. if (A[i] < A[j]) or ( A[i]= A[j] and i < j) then 7. C[j] := 1; 8. else 9. C[j] := 0; 10. for each process P1,j do 11. A[C[j]] := A[j]; 12. end ENUM_SORT