Analysis of Algorithms : An Active Learning Approach

194 PARALLEL ALGORITHMS

You can see in Fig. 7.4 that this process takes 16 parallel steps to sort these

numbers and 1 step to write the results. In general, this process will take 2 *

(N
 1) + 1, or O(N), run time. Because there are N processors the cost of

this sort is O(N^2 ), which is the same as our slower sorts.

E

17 13

12 15

18

P 1 P 2 P 3 P 4 P 5 P 6 P 7 P 8 P 9

F

11 17 15

P 1 P 2 P 3 P 4 P 5 P 6 P 7 P 8 P 9

G

19 12 17 18

P 1 P 2 P 3 P 4 P 5 P 6 P 7 P 8 P 9

H

16

11

11 13 15

12 13 18

12 15 18

19 13 17

P 1 P 2 P 3 P 4 P 5 P 6 P 7 P 8 P 9

I

14

11 12 13 17

16 19 15 18

P 1 P 2 P 3 P 4 P 5 P 6 P 7 P 8 P 9

J 11 12 13 15 18

14 16 19 17

P 1 P 2 P 3 P 4 P 5 P 6 P 7 P 8 P 9

K 11 12 13 15 17

14 16 19 18

P 1 P 2 P 3 P 4 P 5 P 6 P 7 P 8 P 9

■FIGURE 7.4B

A linear parallel

network sort