27.4 A merging network

Our sorting network will be constructed from merging networks, which are networks that can merge two sorted input sequences into one sorted output sequence. We modify BITONIC-SORTER[n] to create the merging network MERGER[n]. As with the bitonic sorter, we shall prove the correctness of the merging network only for inputs that are zero-one sequences. Exercise 27.4-1 asks you to show how the proof can be extended to arbitrary input values.

The merging network is based on the following intuition. Given two sorted sequences, if we reverse the order of the second sequence and then concatenate the two sequences, the resulting sequence is bitonic. For example, given the sorted zero-one sequences X = 00000111 and Y = 00001111, we reverse Y to get Y^R= 11110000. Concatenating X and Y^R yields 0000011111110000, which is bitonic. Thus, to merge the two input sequences X and Y, it suffices to perform a bitonic sort on X concatenated with Y^R.

We can construct MERGER[n] by modifying the first half-cleaner of BITONIC- SORTER[n]. The key is to perform the reversal of the second half of the inputs implicitly. Given two sorted sequences 〈a₁, a₂,...,a_n/2〉 and 〈a_n/2+1, a_n/2+2,..., a_n〉 to be merged, we want the effect of bitonically sorting the sequence 〈a₁, a₂,..., a_n/2, a_n, a_n-1,..., a_n/2+1〉. Since the first half-cleaner of BITONIC-SORTER[n] compares inputs i and n/2 + i, for i = 1, 2,..., n/2, we make the first stage of the merging network compare inputs i and n - i + 1. Figure 27.10 shows the correspondence. The only subtlety is that the order of the outputs from the bottom of the first stage of MERGER[n] are reversed compared with the order of outputs from an ordinary half-cleaner. Since the reversal of a bitonic sequence is bitonic, however, the top and bottom outputs of the first stage of the merging network satisfy the properties in Lemma 27.3, and thus the top and bottom can be bitonically sorted in parallel to produce the sorted output of the merging network.

Figure 27.10: Comparing the first stage of MERGER[n] with HALF-CLEANER[n], for n = 8. (a) The first stage of MERGER[n] transforms the two monotonic input sequences 〈a₁, a₂,...,a_n/2〉 and 〈a_n/2+1, a_n/2+2,...,a_n〉 into two bitonic sequences 〈b₁, b₂,...,b_n/2〉 and 〈b_n/2+1, b_n/2+2,...,b_n〉. (b) The equivalent operation for HALF-CLEANER[n]. The bitonic input sequence 〈a₁, a₂,...,a_n/2-1, a_n/2, a_n, a_n-1,...,a_n/2+2, a_n/2+1〉 is transformed into the two bitonic sequences 〈b₁, b₂,...,b_n/2〉 and 〈b_n, b_n-1,...,b_n/2+1〉.

The resulting merging network is shown in Figure 27.11. Only the first stage of MERGER[n] is different from BITONIC-SORTER[n]. Consequently, the depth of MERGER[n] is lg n, the same as that of BITONIC-SORTER[n].

Figure 27.11: A network that merges two sorted input sequences into one sorted output sequence. The network MERGER[n] can be viewed as BITONIC-SORTER[n] with the first half-cleaner altered to compare inputs i and n - i + 1 for i = 1, 2,..., n/2. Here, n = 8. (a) The network decomposed into the first stage followed by two parallel copies of BITONIC-SORTER[n/2]. (b) The same network with the recursion unrolled. Sample zero-one values are shown on the wires, and the stages are shaded.

Exercises 27.4-1

Prove an analog of the zero-one principle for merging networks. Specifically, show that a comparison network that can merge any two monotonically increasing se quences of 0's and 1's can merge any two monotonically increasing sequences of arbitrary numbers.

Exercises 27.4-2

How many different zero-one input sequences must be applied to the input of a comparison network to verify that it is a merging network?

Exercises 27.4-3

Show that any network that can merge 1 item with n - 1 sorted items to produce a sorted sequence of length n must have depth at least lg n.

Exercises 27.4-4: ★

Consider a merging network with inputs a₁, a₂,..., a_n, for n an exact power of 2, in which the two monotonic sequences to be merged are 〈a₁, a₃,..., a_n-1〉 and 〈a₂, a₄,..., a_n〉. Prove that the number of comparators in this kind of merging network is Φ(n lg n). Why is this an interesting lower bound? (Hint: Partition the comparators into three sets.)

Exercises 27.4-5: ★

Prove that any merging network, regardless of the order of inputs, requires Ω(n lg n) comparators.