Consider the following technique for performing the compare-split operation. Let x1 , x2 , ..., xk be the elements stored at process Pi in increasing order, and let y1 , y2 , ..., yk be the elements stored at process Pj in decreasing order. Process Pi sends x1 to Pj . Process Pj compares x1 with y1 and then sends the larger element back to process Pi and keeps the smaller element for itself. The same procedure is repeated for pairs (x 2 , y2 ), (x3 , y3 ), ..., (xk , yk ). If for any pair (xl , yl ) for 1≤ l≤ k , xl yl , then no more exchanges are needed. Finally, each process sorts its elements.

Required:
a. Show that this method correctly performs a compare-split operation.
b. Analyze its run time, and compare the relative merits of this method to those of the method presented in the text.
c. Is this method better suited for MIMD or SIMD parallel computers?