CS342: Algorithms for Parallel and Distributed Systems Active Exercise #1: Sorting on a Linear Array Given a linear array of P=N processors, design a sorting algorithm that works as follows. The numbers are entered, one at a time, into the leftmost processor; the numbers are to be output in sorted order, one at a time, from the leftmost processor. Analyze the worst-case running time of your algorithm. Is your algorithm a good algorithm? What might this mean in the context of a parallel algorithm? What fundamental limits are there on the performance of any algorithm in this setting? Now assume that the algorithm may begin with all the numbers already input - specifically, one number per processor. Give an algorithm that sorts in this setting. Prove that it is correct and analyze its running time. Is it a good algorithm? What would you do if the number of items to be sorted was much larger than the number of processors? Sorting on a Mesh Give an algorithm that sorts N numbers on a square N-node mesh. (Hint: work with rows and columns, using the algorithms developed in problems 1,2,3, and 4).