I would like to prove that $5$ is the minimal number of comparisons needed to merge two ordered sequences of length $2$ and $5$.
I'm preparing for an Algorithms test and this is a problem that appeared on a previous one.
I've drawn two directed graphs and tried to prove that in the worst case I need at least five additional comparisons (five additional directed edges) to get a Hamiltonian path, but I wasn't able to do that.
We would like to know the number of final states which are possible given the restrictions on the initial condition, i.e. how many increasing orderings of $\{A,B,C,D,E,F,G\}$ are possible, given that $A < B$ and $C <D < E < F < G$.
If we list the variables in increasing order, $A$ and $B$ must replace one or more of the $*$s in $$* \; C \; * \; D \; * \; E \; * \; F \; * \; G \;\; *$$ If each of $A$ and $B$ replaces a single $*$, then there are $\binom{6}{2}$ ways to fit in $A$ and $B$. If both $A$ and $B$ replace a single $*$, the replacement can be done in $\binom{6}{1}$ ways. So the total number of possible final orderings is $$\binom{6}{2} + \binom{6}{1} = 21$$
With $4$ comparisons, the maximum number of output states is $2^4=16$; since $16 < 21$, the sort cannot be done with $4$ comparisons. But with $5$ comparisons, the maximum number of output states is $2^5=32$. Since $21 < 32$, it may be possible to do the merge with $5$ comparisons.
An information-theoretic approach would be to say that resolving the order of the seven items requires $\log_2 21 = 4.46$ bits of information, so at least $5$ comparisons are required.
You still need to show that $5$ comparisons suffice, which I will leave up to you. In other words, I haven't thought about it.
