15.18 The following is a nonrecursive version of MergeSortPRAM.
procedure MergeSortPRAM(L[0:n – 1])
Model: EREW PRAM //the number of processors needed depends on the
//implementation of MergePRAM
Input: L[0:n – 1] (a list of size n = 2k)
of course the initial lists of size 2 are not L[0:1], L[2:3], … , L[n – 2: n – 1], since the list is
split into odd- and even-indexed sublists, as opposed to sublists L[0(n – 1)/2] and L[n/2: n –
1]. In fact, let π : {0, …, n – 1} → {0, …, n – 1} denote the permutation such that
Lπ(0), Lπ(1) , … , Lπ(n-1) is the order in which the list elements occur in leaf nodes of the tree
of recursive calls read from left to right. It turns out that the the k-digit (where k=log2n)
W(n) = W(n/2) + n – 1
= W(n/22) + n(1 + 1/2) – 2
= W(n/23) + n(1 + 1/2 + (1/2)2) – 2
= W(n/2k) + n(1 + 1/2 + (1/2)2 + … + (1/2)k-1) – k
= 0 + n[(1 – (1/2)k)/(1 – 1/2)] – k
15.20 a. The best-case and worst-case complexities of EvenOddMergePRAM are clearly the
same, that is W(n) = B(n). Since EvenOddMergePRAM called with a list of size n performs a
parallelcall with two lists of size n/2 and then performs a single parallel odd-even compare-
15.21 a. We have the following recurrence relation for the best-case, average, and worst-case
complexities:
B(n) = n + 1 + B(n/2), init. cond. B(1) = 0,
A(n) = n + 1 + 1/n[A(0) + A(1) + … + A(n – 1)], init. cond. A(1) = 0
W(n) = n + 1 + W(n – 1), init. cond. W(1) = 0.
Using parallel prefix a 0/1 list A[0:n – 1] can be sorted in logarithmic time as follows. First
copy the elements of A[0:n – 1] into a temporary array Temp[0:n – 1]. Then, for all i such
that Temp[i] = 0, concurrently make the assignment A[a(i) – 1] = Temp[i] where a(i) is the
number of 0’s in Temp[0:i] (to compute a(i) replace 0’s with 1’s and 1’s with 0’s and apply
parallel prefix). For all i such that Temp[i] = 1 concurrently make the assignment A[n –
it is the index i, 0 i n – 2, where Temp[i] ≠ Temp[i+1], or, if no such index exists, then it
is 0 if Temp[1] = 1, otherwise it is n – 1. PartitionPRAM has (logn) complexity. Thus, the
resulting sorting algorithm QuickSortPRAM (where at each level of the recursion all calls to
PartitionPRAM are performed concurrently) has best-case and worst-case complexities
given by
15.22 The following shows the action of OddEvenSort1DMesh for the indicated list. The steps
where an odd-even (resp. even-odd) compare–exchange is performed are labeled “Odd”
(resp. “Even”).
k
0
1
2
3
4
5
6
7
8
9
10
L[k]
18
3
9
2
-11
4
1
-5
19
13
9
Odd
18
3
9
-11
2
1
4
-5
19
9
13
Even
3
18
-11
9
1
2
-5
4
9
19
13
Odd
3
-11
18
1
9
-5
2
4
9
13
19
Even
-11
3
1
18
-5
9
2
4
9
13
19
Odd
-11
1
3
-5
18
2
9
4
9
13
19
Even
-11
1
-5
3
2
18
4
9
9
13
19
Odd
-11
-5
1
2
3
4
18
9
9
13
19
Even
-11
-5
1
2
3
4
9
18
9
13
19
Odd
-11
-5
1
2
3
4
9
9
18
13
19
Even
-11
-5
1
2
3
4
9
9
13
18
19
Odd
-11
-5
1
2
3
4
9
9
13
18
19
15.23 The following shows the action of EvenOddSort1DMesh for the indicated list. The steps
where an even-odd (resp. odd-even) compare-exchange is performed are labeled “Even”
(resp. “Odd”).
k
0
1
2
3
4
5
6
7
8
9
10
L[k]
18
3
9
2
-11
4
1
-5
19
13
9
Even
3
18
2
9
-11
4
-5
1
13
19
9
Odd
3
2
18
-11
9
-5
4
1
13
9
19
Even
2
3
-11
18
-5
9
1
4
9
13
19
Odd
2
-11
3
-5
18
1
9
4
9
13
19
Even
-11
2
-5
3
1
18
4
9
9
13
19
Odd
-11
-5
2
1
3
4
18
9
9
13
19
Even
-11
-5
1
2
3
4
9
18
9
13
19
Odd
-11
-5
1
2
3
4
9
9
18
13
19
Even
-11
-5
1
2
3
4
9
9
13
18
19
Odd
-11
-5
1
2
3
4
9
9
13
18
19
Even
-11
-5
1
2
3
4
9
9
13
18
19
15.24 Since the list has seven elements, we consider the list residing in snake order in the mesh
M3,3, with the last two entries in row 3 containing +. The action of Sort2DMesh is then as
-10 2 11 11 2 -10 9 12 13
-10 -1 2 -10 -1 2 –10 -1 2
15.25 After sorting (snake-order) the list L in Mq,q, n = q2, using Sort2DMesh, we need only
determine the index (i, j) of the middle element if q is odd, or the indices (i1, j1), (i2, j2)
of the two middle elements if q is even. These indices are given by
15.26 Consider the list L in Mq,q where Pi,j:L = 0 for all i,j except the index pairs (n – 2, n – 1)
*15.27
Our adaptation of Batcher’s even-odd merge will be a version presented in the paper
Thompson, C.D, Kung, H.T., Sorting on a Mesh-Connected Parallel Computer,
Communications of the ACM (20) No. 4, 1977, pp. 263-271, and that achieves the same
complexity O(n1/2logn) complexity as Sort2DMesh described on p. 497 in the text. A
Algorithms: Sequential, Parallel and Distributed 1-17
Figure 1.
In Figure 2, we illustrate the interchange steps involved in moving the even-indexed elements
to the left, and the odd-indexed elements to the right.
Figure 2.
To perform an interleave step, one merely does the interchanges illustrated in Figure 2. in
reverse. The number of parallel steps (communications plus compare-exchange steps) is
Figure 3.
We now assume that q ≥ 4. Figure 4 shows the steps to merge two two-column subarrays
assumed to be in snake order into a four column array in snake order (q = 4). The
Algorithms: Sequential, Parallel and Distributed 1-20
It is clear that the number of parallel steps performed by the merging procedure is O(q). A
recursive sorting procedure on Mq,q generalizing EvenOddMergeSortPRAM begins by sorting
each column of in increasing order (using, for example, odd-even transposition sort or the even-
odd merge sort described earlier). Then the columns are divided into the first q/2 and last q/2
15.28 (Changed exercise from 1st printing). Design an O(log2n) algorithm on an EREW
PRAM with O(n/log n) processors for creating a heap.
We parallelize the algorithm CreateMaxHeap2 on page 151 by performing the call to
