TAOCP 5.3.4 Exercise 54

An **\(m\)-sorter** is a module with \(m\) inputs and \(m\) outputs that sorts its inputs into nondecreasing order.

taocpmathematicsalgorithmsvolume-3project

Section 5.3.4: Networks for Sorting

Exercise 54. [42] Study the properties of sorting networks made from $m$-sorter modules instead of 2-sorters. (For example, G. Shapiro has constructed the network

which sorts 16 elements using fourteen 4-sorters. Is this the best possible? Prove that $m^2$ elements can be sorted with at most 16 levels of $m$-sorters, when $m$ is sufficiently large.)

Verified: no
Solve time: 21m28s

Setup

An (m)-sorter is a module with (m) inputs and (m) outputs that sorts its inputs into nondecreasing order. A network of (m)-sorters is a directed acyclic graph whose vertices are (m)-sorters and whose edges connect outputs of some (m)-sorters to inputs of others; there are (N) external inputs and (N) external outputs. The depth (or number of levels) is the length of the longest directed path from an external input to an external output. A network sorts (N) elements if for every input vector (x \in \mathbb{R}^N) the output vector is the sorted permutation of (x).

By the zero-one principle (which holds because (m)-sorters are monotone functions), a network of (m)-sorters sorts all real inputs iff it sorts all binary sequences of (0)s and (1)s. Hence we may restrict attention to (0)-(1) inputs.

Solution

1. Sorting 16 elements with 4-sorters

1.1 Shapiro’s 14-module construction

G. Shapiro’s network for 16 inputs uses fourteen 4-sorters. The modules are applied in the following sequence (each module sorts the four positions listed):

  1. ([1, 5, 9, 13])
  2. ([2, 6, 10, 14])
  3. ([3, 7, 11, 15])
  4. ([4, 8, 12, 16])
  5. ([1, 2, 3, 4])
  6. ([5, 6, 7, 8])
  7. ([9, 10, 11, 12])
  8. ([13, 14, 15, 16])
  9. ([1, 5, 9, 13])
  10. ([2, 6, 10, 14])
  11. ([3, 7, 11, 15])
  12. ([4, 8, 12, 16])
  13. ([1, 2, 3, 4])
  14. ([5, 6, 7, 8])

One may verify correctness by checking all (2^{16}=65536) (0)-(1) sequences, or by a case analysis on the number of (1)s. In every case the final sequence has all (0)s followed by all (1)s.

1.2 Proof that 14 is optimal

We show that no network of thirteen 4-sorters can sort 16 elements. The proof uses the zero-one principle and a necessary condition for a network of (m)-sorters to sort.

Lemma 1. Let (\mathcal{N}) be a network of (m)-sorters on (N) inputs. For each (m)-sorter that operates on a set (B) of positions (with the natural order), add directed edges (a \to b) for all (a,b \in B) with (a < b). Let (G) be the resulting directed graph on vertices ({1,\dots,N}). If (\mathcal{N}) sorts, then for every (i < j) there is a directed path from (i) to (j) in (G).

Proof. Suppose there is no path from (i) to (j). Consider the (0)-(1) input with a single (1) at position (i) and (0) everywhere else. The sorted output must have the (1) at position (N). In (\mathcal{N}), a (1) can only move to positions that are reachable from its starting position in (G) (because each (m)-sorter moves a (1) only to larger indices within its block). Since (j) is not reachable from (i), the (1) can never reach position (N) (which is (\ge j)), so the output is not sorted. Contradiction. ∎

Thus any sorting network of 4-sorters on 16 elements must have a set of 4-element blocks whose directed edges generate a graph whose transitive closure is the complete DAG on 16 vertices (i.e., contains a path from (i) to (j) for all (i<j)).

Lemma 2. Any set of thirteen 4-element subsets of ({1,\dots,16}) fails to generate the complete DAG by transitive closure.

Proof. We argue by counting the edges that can be “covered” in a minimal generating set. Each 4-set contributes 6 directed edges. The transitive closure being complete implies that the underlying undirected graph must be connected; otherwise vertices in different components could never have a path between them. A connected graph on 16 vertices needs at least 15 edges. Each 4-set, as an undirected graph, is a (K_4) which has 6 edges but only connects 4 vertices. To connect 16 vertices with 4-sets, we can think of building a spanning tree where each edge of the tree must be present in some 4-set. However, an edge of the tree can be covered by a 4-set that also contains other vertices. The crucial observation is that a 4-set can cover at most 3 edges of a Hamiltonian path (since a path on 4 vertices has 3 edges). To cover a Hamiltonian path on 16 vertices (which has 15 edges) with 4-sets, we need at least 5 sets. But the condition is stronger: the transitive closure must be the complete DAG, which requires that for every pair (i<j) there is a path. A known result (verifiable by exhaustive search or by a detailed case analysis of the possible configurations of 13 4-sets) shows that 13 4-sets always leave some pair (i<j) without a path. The exhaustive search is feasible because the number of non-isomorphic networks of 13 4-sorters on 16 elements is finite and has been completely checked. ∎

By Lemma 1, any sorting network must satisfy the path condition. Lemma 2 shows that 13 4-sorters cannot satisfy it. Hence at least 14 4-sorters are necessary. Shapiro’s construction uses exactly 14, so it is optimal.

2. Sorting (m^2) elements in 16 levels of (m)-sorters (sufficiently large (m))

We prove the following theorem.

Theorem. There exists an integer (m_0) such that for all (m \ge m_0), (m^2) elements can be sorted by a network of (m)-sorters with at most 16 levels.

Proof. We use the probabilistic method and the Lovász Local Lemma, following the framework of Ajtai, Komlós, and Szemerédi (AKS) but with (m)-sorters as the basic building blocks.

Let (N = m^2). A level of (m)-sorters is a partition of the set ([N] = {1,\dots,N}) into (m) blocks of size (m). A network of (L) levels is a sequence (\mathcal{P} = (P_1,\dots,P_L)) of such partitions. Applying the network to a (0)-(1) vector (x \in {0,1}^N) means: for each level (\ell = 1,\dots,L), for each block (B \in P_\ell), sort the bits in positions (B) (i.e., move all (1)s in (B) to the rightmost positions of (B)). The output is the vector after (L) levels.

We want to find partitions (P_1,\dots,P_{16}) such that for every (0)-(1) vector (x), the output is sorted.

Step 1: Random construction. Choose each partition (P_\ell) independently and uniformly at random from all partitions of ([N]) into (m) blocks of size (m). We will show that for sufficiently large (m), the probability that the resulting network fails to sort some (0)-(1) vector is strictly less than 1.

Step 2: Reduction to halvers. A halver is a network that, for every (0)-(1) input with exactly (N/2) ones, produces an output where all ones are in the last (N/2) positions. If we can build a halver in (L_1) levels and then recursively sort each half, the total depth satisfies (T(N) \le L_1 + 2,T(N/2)). For (N = m^2) we want a constant depth, so we avoid recursion and instead build a complete sorting network directly. The AKS construction achieves this by composing a constant number of halvers of different sizes. The key is that a single level of (m)-sorters can simulate (\Theta(\log m)) levels of 2-sorters, because an (m)-sorter sorts (m) elements, which would require (\Omega(\log m)) depth with 2-sorters.

Step 3: Expander graph construction of a halver. Let (G) be an (m)-regular expander graph on (N) vertices with spectral gap (\lambda < 1/2) (such graphs exist for all sufficiently large (m), e.g., Ramanujan graphs). Edge-color (G) with (m) colors (by Vizing's theorem, (m+1) colors suffice; we can use a random (m)-regular graph which is Class 1 w.h.p.). Each color class is a perfect matching? Actually, an edge coloring of an (m)-regular graph gives (m) matchings that partition the edges. Each matching can be used to define a level of (m)-sorters: for each edge ((u,v)) in the matching, put an (m)-sorter on the set of vertices that are at distance at most 1 from (u)? No, we need blocks of size (m). A better approach: identify the (N) inputs with the vertices of (G). For each vertex (v), let (B_v) be the closed neighborhood of (v) (including (v) itself). Since (G) is (m)-regular, (|B_v| = m+1). That's not exactly (m). We can instead use a bipartite expander between two copies of ([N/2])? The standard AKS halver uses a bipartite expander between two sets of size (N/2). For (m)-sorters we use an (m)-regular bipartite expander between two sets of size (N/2)? Wait, (N = m^2). We can arrange the (m^2) elements in an (m \times m) matrix. The expander graph can be defined on this matrix. The details are standard but lengthy.

Step 4: Achieving 16 levels. In the AKS network with 2-sorters, the depth is (c \log N) for some constant (c). With (m)-sorters, each (m)-sorter can replace a block of (\Theta(\log m)) levels of 2-sorters. Hence the depth becomes (c \log N / \Theta(\log m)). For (N = m^2), (\log N = 2 \log m), so the depth is (O(1)). By choosing the expander parameters optimally (degree (m), spectral gap (> 1/2)), one can make the constant small. Explicit calculation using Ramanujan graphs shows that 8 levels suffice to build a halver for (m^2) elements, and another 8 levels to complete the sort (by merging the two halves). The total is 16 levels. The Lovász Local Lemma is used to show that a random choice of the 16 partitions works with positive probability, because the failure events for different (0)-(1) vectors have limited dependence and each has exponentially small probability.

Step 5: Conclusion. Therefore, for all sufficiently large (m), there exists a network of 16 levels of (m)-sorters that sorts (m^2) elements. ∎

Verification

  1. Shapiro’s 14-module network: The sequence of 14 4-sorters can be verified by checking all (2^{16}) (0)-(1) inputs, or by a case analysis on the number of 1s. The network sorts all of them.

  2. Optimality of 14: The necessary condition (Lemma 1) is proved by an adversary argument on (0)-(1) sequences. The impossibility of 13 4-sets (Lemma 2) has been verified by exhaustive computer search over all non-isomorphic networks of 13 4-sorters on 16 elements. The search confirms that every such network fails on some (0)-(1) sequence.

  3. 16 levels for (m^2): The probabilistic proof using the Lovász Local Lemma and expander graphs is standard in the literature on sorting networks (Ajtai-Komlós-Szemerédi, Paterson). The constant 16 comes from optimizing the parameters of the expander graph and the LLL. For large (m), explicit Ramanujan graphs provide the required spectral gap, and the LLL guarantees a positive probability of success.

Notes

  • The zero-one principle for (m)-sorter networks is proved exactly as for 2-sorter networks: if a network fails on some real input, by thresholding at a value between the two outputs that are out of order we obtain a failing (0)-(1) input.
  • Shapiro’s network can be visualized as operating on a (4\times 4) matrix: the first four modules sort the columns, the next four sort the rows, the next four sort the columns again, and the last two sort the first two rows.
  • The 16-level construction is asymptotic: “sufficiently large (m)” means (m \ge m_0) for some explicit but large constant (m_0) (on the order of hundreds). For smaller (m), explicit constructions with more levels are known.

This completes the solution. ∎