## Performance and scalability of ShearSort

1. Give expressions for parallel time T(N,p), cost C(N,p) and efficiency E(N,p) of ShearSort for sorting N numbers on a mesh of p processors M(\sqrt{p},\sqrt{p}), 1<= p<= N. Assume that the operation Compare&Split of two sorted sequences of k numbers performed by two adjacent processors takes time k.
2. Given a constant 0 < E0 < 1, determine asymptotically minimum function f1 such that
for all  np=\Omega(f1(p)) is E(np,p)>= E0.

3. Similarly, determine asymptotically maximum function f2 such that
for all  pn=O(f2(n)) is E(n,pn)>= E0.

4. What is the scalability of this algorithm?