1. Show that there are ( − 1) communications for a transpose operation on a × array, as stated in Section XXXXXXXXXXWrite a parallel program to implement shearsort. 2. Prove that the time complexity...

1. Show that there are ( − 1) communications for a transpose operation on a × array, as stated in Section 10.3.1. 10-8. Write a parallel program to implement shearsort.

2. Prove that the time complexity of odd-even mergesort is Ο(log2 n) with n processors.