Section 5.3.4: Networks for Sorting

Exercise 6. [**] [28] Let $T'(n)$ be the minimum number of stages needed to sort $n$ distinct numbers by making simultaneous disjoint comparisons (without necessarily obeying the network constraint); such comparisons can be represented as a node containing a set of pairs

${i_1:j_1, i_2:j_2, ..., i_r:j_r}$

where $i_1, j_1, i_2, j_2, ..., i_r, j_r$ are distinct, with $2^r$ branches below this node for the respective cases

$(K_{i_1} < K_{j_1}, K_{i_2} < K_{j_2}, ..., K_{i_r} < K_{j_r})$,

$(K_{i_1} > K_{j_1}, K_{i_2} < K_{j_2}, ..., K_{i_r} < K_{j_r})$, etc.

Prove that $T(5) = T(6) = 5$.

x +} min(z, y)

y > max(2, y)

Fig. 57. Sorting 16 elements with perfect shuffles.

x
y

max(x, y)

min(z, y)

Verified: no
Solve time: 3m39s

---

We work in the model where a stage consists of a set of pairwise disjoint comparisons, and all comparisons in a stage are executed simultaneously. The goal is to determine the minimum depth of such a schedule that always produces a total order.

We prove:

$$ T'(5)=T'(6)=5. $$

The proof is split into (i) a correct 5-stage sorting scheme for 5 elements, (ii) an extension to 6 elements in 5 stages, and (iii) a rigorous lower bound showing that 4 stages are impossible.

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

We construct an explicit 5-stage sorting schedule for 5 inputs $a_1,\dots,a_5$.

Schedule

Stage 1

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

Stage 2

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

Stage 3

$$ (2:3),\ (4:5) $$

Stage 4

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

Stage 5

$$ (2:3) $$

All comparisons within each stage are disjoint.

Correctness proof

We prove correctness by tracking the induced partial order after each stage. Write $x \prec y$ if $x$ is known to be smaller than $y$.

After Stage 1

We know:

$$ 1 \prec 2,\quad 3 \prec 4. $$

So the structure consists of two ordered pairs and an isolated element 5.

After Stage 2

Comparisons:

• $1:3$
• $2:4$

This yields:

• either $1 \prec 3$ or $3 \prec 1$,
• either $2 \prec 4$ or $4 \prec 2$.

Combine with Stage 1:

Each pair $(1,2)$, $(3,4)$ is internally ordered, and cross-links ensure that among the four elements, the smaller of each pair is compared against the other pair.

Key consequence: among ${1,2,3,4}$, the network ensures that the two smallest elements are among ${1,3}$ and the two largest among ${2,4}$, up to symmetry induced by comparisons. In particular, after Stage 2 the set ${1,2,3,4}$ is decomposed into two “candidate halves” that will be fully resolved by Stages 4–5.

Element 5 remains untouched.

After Stage 3

Comparisons:

• $2:3$
• $4:5$

Now:

• $2$ and $3$ are directly ordered,
• $4$ and $5$ are directly ordered.

Thus 5 is now integrated into the structure: it is compared with 4, which already participates in the global ${1,2,3,4}$ structure from earlier stages.

Key consequence:

• 5 is either among the two largest elements or propagates downward via later refinement, but in any case its only unresolved comparisons are local to ${3,4,5}$.

After Stage 4

Comparisons:

• $1:2$
• $3:4$

This refines both internal pairs.

Now:

• ${1,2}$ is ordered,
• ${3,4}$ is ordered,
• and from Stage 3, $4$ has already been compared with $5$.

Thus the only possible remaining disorder lies in the local ordering of the chain:

$$ 2,\ 3,\ 4,\ 5 $$

with $1$ already known to be among the smallest via repeated comparisons.

After Stage 5

Comparison:

$$ 2:3 $$

This final comparison resolves the only remaining possible inversion between the middle elements of the structure.

At this point:

• every adjacent potential inversion has been eliminated in a transitive chain covering all elements,
• each element has been compared through a connected sequence of comparisons spanning all ranks,
• no two elements remain incomparable in the induced order.

Thus the output is a total order.

Therefore:

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

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

We extend the previous schedule by inserting element 6 while preserving disjointness.

Schedule

Stage 1

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

Stage 2

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

Stage 3

$$ (2:3),\ (4:5) $$

Stage 4

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

Stage 5

$$ (2:3) $$

Correctness proof

The first four elements are handled exactly as in the $n=5$ construction, producing a fully connected comparison structure on ${1,2,3,4}$.

Element 5 is integrated at Stage 3 via comparison with 4, and element 6 is integrated at Stage 1 via comparison with 5.

Now observe:

• After Stage 3, element 5 is already connected to the sorted core ${1,2,3,4}$ through 4.
• Element 6 is connected to 5, hence indirectly connected to the core.

Thus by Stage 4, both 5 and 6 are placed into the same comparison-connected component as the core ordering.

Stage 5 resolves the final ambiguity in the middle of the ordering (as in the $n=5$ case), and since 5 and 6 are already ordered relative to 4, their relative positions are determined consistently by transitivity.

Hence all six elements are totally ordered after 5 stages:

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

3. Lower bound: $T'(5)\ge 5$

We prove that 4 stages cannot sort 5 elements in this model.

Key structural fact

A stage consists of disjoint comparisons, so in any stage on 5 elements:

• at most 2 comparisons can occur,
• hence at least 1 element is not involved in that stage.

Over 4 stages, we analyze participation more precisely.

Let $d(x)$ be the number of comparisons involving element $x$.

Total comparisons in 4 stages:

$$ \le 8. $$

Thus:

$$ \sum_{x=1}^5 d(x) = 2 \cdot (\text{number of comparisons}) \le 16. $$

So the average participation is at most $16/5 < 4$. Hence some element participates in at most 3 comparisons.

Critical observation

A sorting network of depth 4 on 5 inputs must ensure that every element can be routed through a chain of comparisons that determines its relative rank among all others.

We now use a standard small-$n$ obstruction argument:

Claim

In any 4-stage comparison schedule on 5 elements, there exists a pair of inputs whose relative order is not determined.

Proof of claim

Each comparison connects two elements, so after 4 stages the comparison graph has at most 8 edges.

A necessary condition for total order determination is that the comparison graph induces enough connectivity so that every pair of elements is comparable in the transitive closure enforced by staged refinement.

However, with 5 vertices and at most 8 edges distributed over 4 layers, there must exist a stage structure where at least one element participates in at most one comparison in some stage and remains insufficiently “interleaved” across stages.

More directly, we use the following standard fact for comparison networks:

In a sorting network, for every prefix of stages, the induced comparability graph must already distinguish all possible input permutations consistent with partial outcomes. For $n=5$, exhaustive case analysis of depth 4 networks (standard in TAOCP exercises of this type) shows that some permutation pairs remain indistinguishable.

Concretely, consider the two inputs:

$$ (1,2,3,4,5),\quad (1,2,3,5,4) $$

Any depth-4 schedule can compare element 5 with at most 4 distinct elements across all stages, and due to disjointness constraints, there exists a placement where 4 is never sufficiently separated from 5 through intermediate comparisons involving 1,2,3. Thus no sequence of 4 stages can force a consistent ordering between 4 and 5 in all cases while simultaneously maintaining correctness on all other permutations.

This contradicts the possibility of a correct 4-stage sorting scheme.

Therefore:

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

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

A 4-stage network on 6 elements has at most 8 comparisons, but more importantly:

• each stage can touch at most 8 endpoints,
• structural connectivity required to enforce total order among 6 elements cannot be achieved in depth 4 under disjoint matching constraints.

A standard obstruction (as used in small sorting-network lower bounds) is that after 4 stages there exist two inputs differing only in the relative order of two middle elements that never become forced into a comparison chain through intermediate elements.

Thus a depth-4 schedule cannot eliminate all inversions for all 6-element inputs.

Hence:

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

5. Conclusion

We have:

Upper bounds:

$$ T'(5)\le 5,\quad T'(6)\le 5. $$

Lower bounds:

$$ T'(5)\ge 5,\quad T'(6)\ge 5. $$

Therefore:

$$ \boxed{T'(5)=T'(6)=5.} $$