Analysis of Algorithms : An Active Learning Approach

7.5 PARALLEL SORTING 197

There are parallel merge techniques that are beyond the level of this text

that can merge two lists with an optimal cost of O(N) using no more than N /

lgN processors. If we divide the list into N / lg N pieces and then sort these

using an efficient sequential sort, like quicksort, we can use a parallel merge

technique to recombine the pieces into one list. We could also use a parallel

merge algorithm to construct a parallel version of merge sort.

7.5.4

1. Write a formal parallel algorithm for the counting sort as described in Sec-
   tion 7.5.3. Analyze your algorithm for both its speed and its cost.


2. Write an algorithm for merge sort as described in Section 3.6, using the call
   ParallelMergeLists(i, j, k, l) to represent the invocation of the
   parallel merge that combines the sublist in locations Mi through Mj and the
   sublist in locations Mk through Ml. Analyze your algorithm for both its speed
   and its cost. You can assume that ParallelMergeLists takes lg N + 1
   steps using N processors, where N is the number of elements in the resulting
   list (N = j
   i + l
   k + 2).

15 18 13 12 17 11 19 16 14

O1 15 18 12 13 11 17 16 19 14

E1 15 12 18 11 13 16 17 14 19

O2 12 15 11 18 13 16 14 17 19

E2 12 11 15 13 18 14 16 17 19

O3 11 12 13 15 14 18 16 17 19

E3 11 12 13 14 15 16 18 17 19

O4 11 12 13 14 15 16 17 18 19

E4 11 12 13 14 15 16 17 18 19

■FIGURE 7.5

The odd-even

parallel sort

■7.5.4 EXERCISES