196 PARALLEL ALGORITHMS
if they are out of order then
swap them
end if
end for k
Parallel End
Parallel Start
for k = 1 to N/2-1 do
Pk compares M2k and M2k+1
if they are out of order then
swap them
end if
end for k
Parallel End
end for j
On each pass, this algorithm will first compare M 1 and M 2 ,M 3 and M 4 ,... ,
MN 1 and MN and then compare M 2 and M 3 ,M 4 and M 5 ,... , MN 2 and
MN 1 , swapping those that are out of order. So, imagine that the smallest value
is in the last position. The first comparison will move it into the second to last
position, and then the second comparison will move it into the third to last
position. Each pass of the algorithm moved this element two positions closer to
where it should be. The fact that the algorithm loops N / 2 times will move
this element N 1 positions forward and into the correct position.
Figure 7.5 shows this sorting process on our list of 15, 18, 13, 12, 17, 11,
19, 16, and 14. Each of the rows shows the result of either an odd (labeled with
O) or and even (labeled with E) pass through the list.
Because the comparisons are done in parallel, each pass of the loop does two
comparisons, so the overall run time of this algorithm is O(N). The cost will
beN / 2 *O(N), which is smaller than our linear network attempt but is still
O(N^2 ).■ 7.5.3 Other Parallel Sorts
We can also sort a list of values that are unique by a counting method. If we
compare each value with the entire list and count how many numbers are less
than this value, we will get the number of list elements that must occur before
this one in the sorted list. We can then use this count plus 1 as the location in
the list for this value. If we use the CREW PRAM model, with one processor
for each data value, we can identify the location for each value in O(N) com-
parisons. Because we need N processors, the cost of this technique is O(N^2 ).