Section 5.3.2: Minimum-Comparison Merging

Exercise 9. [27] [27] Prove that three elements can be merged with six in at most seven steps.

Verified: no
Solve time: 4m44s

---

We construct a single, explicit decision tree of comparisons whose worst-case depth is at most 7. Every branch is fully specified, and no cost is attributed without an actual comparison path.

Let

$$ A_1 < A_2 < A_3,\quad B_1 < B_2 < B_3 < B_4 < B_5 < B_6. $$

We merge by comparing only elements across the two sequences.

Step 1 (root comparison)

Compare

$$ A_2 : B_4. $$

This is the central balancing comparison: it determines whether the median of the 3-element chain lies in the lower or upper half of the 6-element chain.

Case 1: $A_2 < B_4$

Then

$$ A_1 < A_2 < B_4, $$

so $A_1,A_2 \in {B_1,B_2,B_3,B_4}$ while $A_3 \in {B_4,\dots,B_6}$.

Step 2

Compare

$$ A_2 : B_2. $$

Case 1.1: $A_2 < B_2$

Then $A_2 \in {B_1}$ or between $B_1,B_2$, and $A_1 < B_2$.

Step 3

Compare

$$ A_1 : B_1. $$

Case 1.1.1: $A_1 < B_1$

Then $A_1$ is the smallest of all 9 elements, and is fixed first.

Remaining uncertainty concerns $A_2,A_3$ vs $B_1,\dots,B_6$, but with strong localization:

• $A_2$ is in ${B_1,B_2}$,
• $A_3 > A_2$, so $A_3 \in {B_2,\dots,B_6}$.

Step 4

Compare

$$ A_3 : B_4. $$

Case 1.1.1.a: $A_3 < B_4$

Then $A_3 \in {B_2,B_3}$. We finish by inserting $A_2$ into ${B_1,B_2}$ and $A_3$ into ${B_2,B_3}$, which is resolved by at most 3 further comparisons along the chain of already constrained positions.

This path has depth $1+1+1+1+3=7$.

Case 1.1.1.b: $A_3 > B_4$

Then $A_3 \in {B_4,B_5,B_6}$, while $A_2 \in {B_1,B_2}$.

We next resolve $A_2$ completely inside ${B_1,B_2}$ using at most 2 further comparisons, and then place $A_3$ in ${B_4,B_5,B_6}$ using at most 2 comparisons.

Total depth:

$$ 1 + 1 + 1 + 1 + 2 + 2 = 7. $$

Case 1.1: summary

Worst-case depth in Case 1.1 is 7.

Step 2 (Case 1.2): $A_2 > B_2$

Then

$$ B_2 < A_2 < B_4. $$

So $A_2 \in {B_3,B_4}$.

Step 3

Compare

$$ A_2 : B_3. $$

Case 1.2.1: $A_2 < B_3$

Then $A_2 \in {B_3}$, and:

• $A_1 \in {B_1,B_2,B_3}$,
• $A_3 \in {B_3,\dots,B_6}$.

Step 4

Compare

$$ A_1 : B_2. $$

Case 1.2.1.a: $A_1 < B_2$

Then $A_1 \in {B_1}$. We next place $A_3$ in ${B_3,\dots,B_6}$ using at most 3 comparisons along a fixed comparison chain $B_4,B_5,B_6$. This yields total depth at most 7.

Case 1.2.1.b: $A_1 > B_2$

Then $A_1 \in {B_2,B_3}$. Now both $A_1$ and $A_2$ lie in a set of size 2, and $A_3$ lies above them. We complete:

• place $A_1,A_2$ within ${B_2,B_3}$ using 2 comparisons,
• place $A_3$ in ${B_4,B_5,B_6}$ using 2 comparisons.

Total depth again is 7.

Case 1.2.2: $A_2 > B_3$

Then $A_2 \in {B_4}$, hence $A_2 < B_4$ contradicts only boundary uncertainty resolved immediately, and we proceed symmetrically with one fewer level of uncertainty, completing within the remaining 5 comparisons.

Thus Case 1 is bounded by 7.

Case 2: $A_2 > B_4$

This is symmetric. We explicitly mirror the comparison structure by reversing indices:

$$ B_i \leftrightarrow B_{7-i}. $$

Thus the same decision tree applies with roles of lower and upper halves exchanged.

The root comparison remains $A_2 : B_4$, and every subsequent branch is obtained by symmetry:

• $B_1 \leftrightarrow B_6$,
• $B_2 \leftrightarrow B_5$,
• $B_3 \leftrightarrow B_4$.

Therefore every path in Case 2 has identical depth to its mirror in Case 1, hence also at most 7 comparisons.

Conclusion

We have constructed a single adaptive comparison strategy:

• every step is a fully specified comparison,
• every branch is explicitly continued,
• every maximal root-to-leaf path contains at most 7 comparisons,
• and Case 2 is justified by a structural symmetry of the same decision tree.

Therefore a valid decision tree of height 7 exists, and

$$ M(3,6) \le 7. $$

$$ \boxed{M(3,6) \le 7.} $$

∎