Assume that you have a computer with an unbounded number of processors
that can work in parallel. Write a parallel algorithm that sorts n keys,
based on the sequential mergesort algorithm, using as many processors as
possible in each sorting round, so as to minimize the number of rounds
required until all the keys at input are sorted. Assume that n is a power
of 2. Write your algorithm in schematic form only.
a. How many rounds are required by your algorithm?
b.What is the parallel complexity of every eound? (Count the maximal number of
comparisons performed by a single processor activated in that round).
c. What is the parallel complexity of your algorithm (summing up the parallel
complexities of all the rounds)?