7.5 PARALLEL SORTING 195■ 7.5.2 Odd-Even Swap Sort
In previous sections, we were able to reduce costs by reducing the number of
processors. We can cut the number of processors needed in half with the fol-
lowing sorting method, which compares adjacent values and swaps them if
they are out of order.
for j = 1 to N/2 do
Parallel Start
for k = 1 to N/2 do
Pk compares M2k-1 and M2kL14 1611 12 13 15 17 1819P 1 P 2 P 3 P 4 P 5 P 6 P 7 P 8 P 9M15 17 19P 1 P 2 P 3 P 4 P 5 P 6 P 7 P 8 P 9N16 18P 1 P 2 P 3 P 4 P 5 P 6 P 7 P 8 P 9O 1111 12 13 14 15 17 1911 12 13 14 16 1812 13 14 15 16 1817 19P 1 P 2 P 3 P 4 P 5 P 6 P 7 P 8 P 9P 11 12 13 14 15 16 17 1918P 1 P 2 P 3 P 4 P 5 P 6 P 7 P 8 P 9Q11 12 13 14 15 16 17 18 19P 1 P 2 P 3 P 4 P 5 P 6 P 7 P 8 P 9
■FIGURE 7.4C
A linear parallel
network sort