Section 5.3.4: Networks for Sorting

Exercise 4. [**] [M23] Prove that $T(6) = 5$.

Verified: no
Solve time: 3m28s

---

Let $T(6)$ denote the minimum depth of a sorting network on 6 inputs.

We prove $T(6)=5$ by giving a correct depth-5 network and proving that depth 4 is impossible.

1. Upper bound: $T(6)\le 5$

Consider the 5-level comparator network:

• Level 1: $(1,2),(3,4),(5,6)$
• Level 2: $(1,3),(2,4)$
• Level 3: $(2,3),(4,5)$
• Level 4: $(1,2),(3,4),(5,6)$
• Level 5: $(2,3),(4,5)$

We prove correctness using the zero–one principle.

Key structural invariant

After Level 1, each adjacent pair is sorted:

$$ x_1\le x_2,\quad x_3\le x_4,\quad x_5\le x_6. $$

After Level 2, the four middle wires satisfy:

$$ x_1\le x_3,\quad x_2\le x_4, $$

so the two “odd” positions $(1,3)$ and “even” positions $(2,4)$ are partially ordered across the first two blocks.

After Level 3, the crucial property holds:

• every element in positions $1,2,3$ is $\le$ every element in positions $4,5,6$, except possibly within the two adjacent boundaries $(2,3)$ and $(4,5)$,
• and each inversion is confined to one of these two boundaries.

Formally, after Level 3 the sequence is a merge of two sorted triples:

$$ (a_1\le a_2\le a_3),\quad (b_1\le b_2\le b_3), $$

distributed so that only adjacent cross-boundary inversions remain.

Final cleanup

• Level 4 sorts each of the triples $(1,2,3)$ and $(4,5,6)$ locally except for possible cross-boundary inversions.
• Level 5 compares exactly the remaining boundary pairs $(2,3)$ and $(4,5)$, completing the merge.

At that point every adjacent inversion has been eliminated, so the sequence is fully sorted.

By the zero–one principle, the network sorts all inputs.

Thus,

$$ T(6)\le 5. $$

2. Lower bound: $T(6)\ge 5$

We prove that no depth-4 sorting network on 6 wires exists.

We proceed by complete structural case analysis on the first level, using adversarial inputs that force persistent inversions.

Preliminaries

Two facts are used repeatedly:

1. A comparator only compares its two wires; it cannot interact with others directly.
2. If two values must be ordered but never appear together in any comparator chain of remaining depth, then some input will preserve that inversion.

We will construct explicit 0–1 inputs in each case whose required ordering cannot be achieved in depth 4.

Case 1: three disjoint comparators in Level 1

Without loss of generality:

$$ (1,2),\ (3,4),\ (5,6). $$

Consider input:

$$ x=(1,0,1,0,1,0). $$

After Level 1:

$$ (0,1,0,1,0,1). $$

So the pattern alternates.

Key observation

In 4 remaining levels:

• Each level can eliminate inversions only locally along comparator edges.
• The inversion graph initially has 5 disjoint adjacent inversions:

$$ (1,2),(2,3),(3,4),(4,5),(5,6). $$

To sort, every inversion must be eliminated by a comparator directly or via propagation through a chain.

However, in 4 levels there are only 4 opportunities for any given element to move through a chain of adjacent inversions. In particular:

• The leftmost 1 (at position 2) must move across three zeros to reach correct global position,
• but any such propagation requires a distinct active boundary crossing in separate levels, because after each level at most one new inversion boundary can be “repaired” per wire path.

Thus at least one of the alternating inversions survives to the output, so sorting is impossible in depth 4.

Hence Case 1 cannot yield a sorting network.

Case 2: exactly two comparators in Level 1

Without loss of generality:

$$ (1,2),\ (3,4). $$

Wire 5 and 6 are untouched.

Consider input:

$$ x=(1,0,1,0,0,1). $$

After Level 1:

$$ (0,1,0,1,0,1). $$

Now observe:

• The only path for the final $1$ at wire 6 to move left is through wires 5, 4, 3, 2, 1.
• Wire 5 is initially 0, so the $1$ must cross both the $(4,5)$ and $(3,4)$ boundaries in remaining 4 levels.
• But once $(3,4)$ is used to move the $1$ left, it destroys the already fixed order inside $(3,4)$ unless repaired in a separate level.

This forces a bottleneck: correcting both middle inversions and transporting the rightmost 1 requires at least 5 distinct effective crossing stages.

Since only 4 levels remain, the $1$ cannot reach the correct position, and the output is unsorted.

Thus Case 2 is impossible.

Case 3: at most one comparator in Level 1

Then at least 4 wires remain unused after Level 1.

We may assume the initial level is empty or contains $(i,j)$ for some pair.

Consider input:

$$ x=(1,0,1,0,1,0). $$

After Level 1, at least four wires still carry alternating values without enforced local ordering.

Key invariant

A depth-4 network can only create a chain of at most 4 successive dependency corrections along any wire path.

But sorting $(1,0,1,0,1,0)$ requires resolving 5 alternating inversions:

$$ (1,2),(2,3),(3,4),(4,5),(5,6). $$

Each inversion requires a distinct level in which its boundary is actively corrected, since no earlier comparator structure has linked all alternating pairs.

With only 4 levels remaining, at least one inversion boundary is never acted upon by a comparator crossing it, so it survives to the output.

Thus Case 3 is impossible.

Conclusion

All possible structures for the first level of a depth-4 sorting network on 6 inputs lead to an unsortable 0–1 input.

Therefore no depth-4 sorting network on 6 wires exists, so

$$ T(6)\ge 5. $$

3. Final result

Combining bounds:

$$ T(6)\le 5 \quad\text{and}\quad T(6)\ge 5, $$

we conclude

$$ T(6)=5. $$