How many comparators are there in SORTER[n]?

Show that the depth of SORTER[n] is exactly (lg n)(lg n + 1)/2.

Suppose that we have 2n elements 〈a₁, a₂,..., a_2n〉 and wish to partition them into the n smallest and the n largest. Prove that we can do this in constant additional depth after separately sorting 〈a₁, a₂,..., a_n〉 and 〈a_n+1, a_n+2,..., a_2n〉.

Let S(k) be the depth of a sorting network with k inputs, and let M(k) be the depth of a merging network with 2k inputs. Suppose that we have a sequence of n numbers to be sorted and we know that every number is within k positions of its correct position in the sorted order. Show that we can sort the n numbers in depth S(k) + 2M(k).

We can sort the entries of an m × m matrix by repeating the following procedure k times:

1. Sort each odd-numbered row into monotonically increasing order.

2. Sort each even-numbered row into monotonically decreasing order.

3. Sort each column into monotonically increasing order.

How many iterations k are required for this procedure to sort, and in what order should we read the matrix entries after the k iterations to obtain the sorted output?

A comparison network is a transposition network if each comparator connects adjacent lines, as in the network in Figure 27.3.

1. Show that any transposition sorting network with n inputs has Ω(n²) comparators.

2. Prove that a transposition network with n inputs is a sorting network if and only if it sorts the sequence 〈n, n - 1,..., 1〉. (Hint: Use an induction argument analogous to the one in the proof of Lemma 27.1.)

An odd-even sorting network on n inputs 〈a₁,a₂,...,a_n〉 is a transposition sorting network with n levels of comparators connected in the "brick-like" pattern illustrated in Figure 27.13. As can be seen in the figure, for i = 1, 2,..., n and d = 1, 2,..., n, line i is connected by a depth-d comparator to line j = i + (-1)^i+d if 1 ≤ j ≤ n.

Figure 27.13: An odd-even sorting network on 8 inputs.

3. Prove that odd-even sorting networks actually sort.

In Section 27.4, we saw how to construct a merging network based on bitonic sorting. In this problem, we shall construct an odd-even merging network. We assume that n is an exact power of 2, and we wish to merge the sorted sequence of elements on lines 〈a₁, a₂,..., a_n〉 with those on lines 〈a_n+1, a_n+2,..., a_2n〉. If n = 1, we put a comparator between lines a₁ and a₂. Otherwise, we recursively construct two odd-even merging networks that operate in parallel. The first merges the sequence on lines 〈a₁, a₃,..., a_n-1〉 with the sequence on lines 〈a_n+1, a_n+3,..., a_2n-1〉 (the odd elements). The second merges 〈a₂, a₄,..., a_n〉 with 〈a_n+2, a_n+4,..., a_2n〉 (the even elements). To combine the two sorted subsequences, we put a comparator between a_2i and a_{2i + 1} for i = 1, 2,..., n - 1.

1. Draw a 2n-input merging network for n = 4.

2. Professor Corrigan suggests that to combine the two sorted subsequences produced by the recursive merging, instead of putting a comparator between a_2i and a_2i+1 for i = 1, 2,..., n - 1, one should put a comparator between a_2i-1 and a_2i for i = 1, 2,..., n. Draw such a 2n-input network for n = 4, and give a counterexample to show that the professor is mistaken in thinking that the network produced is a merging network. Show that the 2n-input merging network from part (a) works properly on your example.

3. Use the zero-one principle to prove that any 2n-input odd-even merging network is indeed a merging network.

4. What is the depth of a 2n-input odd-even merging network? What is its size?

A permutation network on n inputs and n outputs has switches that allow it to connect its inputs to its outputs according to any of the n! possible permutations. Figure 27.14(a) shows the 2-input, 2-output permutation network P₂, which consists of a single switch that can be set either to feed its inputs straight through to its outputs or to cross them.

Figure 27.14: Permutation networks. (a) The permutation network P₂, which consists of a single switch that can be set in either of the two ways shown. (b) The recursive construction of P₈ from 8 switches and two P₄'s. The switches and P₄'s are set to realize the permutation π = 〈4, 7,3, 5,1, 6, 8, 2〉.

1. Argue that if we replace each comparator in a sorting network with the switch of Figure 27.14(a), the resulting network is a permutation network. That is, for any permutation π, there is a way to set the switches in the network so that input i is connected to output π(i).

Figure 27.14(b) shows the recursive construction of an 8-input, 8-output permutation network P₈ that uses two copies of P₄ and 8 switches. The switches have been set to realize the permutation π = 〈π(1), π(2),..., π(8)〉 = 〈4, 7, 3, 5, 1, 6, 8, 2〉, which requires (recursively) that the top P₄ realize 〈4, 2, 3, 1〉 and the bottom P₄ realize 〈2, 3, 1, 4〉.

2. Show how to realize the permutation 〈5, 3, 4, 6, 1, 8, 2, 7〉 on P₈ by drawing the switch settings and the permutations performed by the two P₄'s.

Let n be an exact power of 2. Define P_n recursively in terms of two P_n/2's in a manner similar to the way we defined P₈.

3. Describe an O(n)-time (ordinary random-access machine) algorithm that sets the n switches connected to the inputs and outputs of P_n and specifies the permutations that must be realized by each P_n/2 in order to accomplish any given n-element permutation. Prove that your algorithm is correct.

4. What are the depth and size of P_n? How long does it take on an ordinary random-access machine to compute all switch settings, including those within the P_n/2's?

5. Argue that for n > 2, any permutation network-not just P_n-must realize some permutation by two distinct combinations of switch settings.