Questions 1 and 2 are related to the chapter Parallel Sorting Algorithms
whereas Question 3 is related to both the introductory chapter
Parallel Scientific Computing: Models, Algorithms and Implementation.
and the chapter Performances and scalability of parallel algorithms.
For all questions,
we rely on the PRAM model and neglect all communication costs.
Marc Moreno Maza