This is part of self-study.
What is the least number of comparisons needed to merge any two lists in increasing order into one list in increasing order when the number of elements in the two lists are
a) 1, 4? b) 2, 4? c) 3, 4? d) 4, 4?
For part a (1, 4), the book I'm using suggests that, to add one element to a list of n elements, binary search can be used to search for the position in which to insert the element, which would take $\left \lceil log_2 n \right \rceil$ comparisons. In this case (two lists with 1 and 4 elements, respectively), the number of comparisons made by the binary search would be $\left \lceil log_2 4 \right \rceil = 2$. Then, since there are five possible insertion points, one more comparison would be needed to find where to put the element (as was pointed out below in the comments). So, in total, 3 comparisons are needed.
But I'm not sure what to do with the other cases. For part b, to insert the two elements $a_1$ and $a_2$ into the list $\{b_1,b_2,b_3,b_4\}$, I could also use binary search. For inserting $a_1$, it would take 3 comparisons, like in the first case. Now I have to insert $a_2$ into the newly formed 5 element list, which contains $a_1$. I could do another binary search, but, this time, I don't need to do the binary search for the whole 5 elements list, because, since $a_2$ is greater than $a_1$ (because both lists are ordered), I can exclude $a_1$ and all elements previous to $a_1$ from the search, because $a_2$ will be certainly greater than them all.
So, I think I should consider the worst case, in which $a_1$ will have been inserted in the beginning of the list (that is, the 5 elements list will be $\{a_1,b_1,b_2,b_3,b_4\}$. In this case, the second binary search will be done for a list of 4 elements, so it will take 3 comparisons. Thus, for part b, two lists, with 2 and 4 elements, respectively, can be merged with a total of 6 comparisons in the worst case.
Notice that I am considering the worst case here because the question asks for the least number of comparisons for any two lists of 2 and 4 elements.
As an example for part b, consider the lists $\{1, 2\}$ and $\{3, 4, 5, 6\}$. The first binary search will insert 1 in the beginning of the second list, giving the list $L = \{1, 3, 4, 5, 6\}$. The second binary search will be done in the sublist $\{3, 4, 5, 6\}$ of the list L and will insert 2 in the beginning of this sublist: $\{2, 3, 4, 5, 6\}$. Thus, the final list is $\{1, 2, 3, 4, 5, 6\}$.
However, since the book I'm using states that the upper bound for merging two lists with m and n elements is $m + n – 1$ comparisons, it seems that I can't use this binary search technique here, because the upper bound for merging the 2 and 4 element lists would be 5 comparisons, which is less than the 6 comparisons needed by the technique above.
Is there some way to use fewer comparisons?
Thank you in advance.
joriki: Thank you for the answer. I understand why $m+n-1$ is the upper bound. But, in the original post, I found a strategy for case a (where the list are of 1 and 4 elements) that gives a number of comparisons which is lower than $m+n-1$ for any two lists of sizes 1 and 4; I couldn't find such strategy for the (2, 4), (3, 4) and (4, 4) cases. Maybe, for each one of these three other cases, there is no strategy that guarantees a number of comparisons smaller than (m+n-1) to merge any two lists. But I have no clue how to prove it…
Any hints?
Best Answer
The bound $m+n-1$ is achieved by a linear merge: Start with a pointer at the beginning of each list, compare the two elements pointed to, add the smaller one to the merged list and increase that pointer. In case you have to compare the last two elements, you've made $(m-1)+(n-1)$ comparisons to get to that point, so the worst case takes $m+n-1$ operations.
[Edit in response to the edit in the question:]
For simplicity, let's assume that all values are different so that all comparisons have a binary result. (Since this is about worst-case behaviour, we can make arbitrary assumptions about the input.) With $k$ binary results, you can distinguish at most $2^k$ different cases. The result of merging two sorted lists of lengths $m$ and $n$ can be specified by the positions of the $m$ elements of the one list in the merged list, and there are $\binom{m+n}m$ different arrangements of these positions. Thus you need at least $\left\lceil\log_2\binom{m+n}m\right\rceil$ comparisons. That solves cases c) and d), since
$$\left\lceil\log_2\binom{3+4}3\right\rceil=\left\lceil\log_235\right\rceil=6=3+4-1$$
and
$$\left\lceil\log_2\binom{4+4}4\right\rceil=\left\lceil\log_270\right\rceil=7=4+4-1\;.$$
Case b) needs a bit more work, since
$$\left\lceil\log_2\binom{2+4}2\right\rceil=\left\lceil\log_215\right\rceil=4\lt2+4-1\;.$$
To allow the merge to be done with $4$ comparisons, the first comparison would have to divide the $15$ possibilities into two groups of $8$ and $7$; otherwise one of the groups would have more than $8$ possibilities and couldn't be resolved with the remaining $3$ comparisons. Due to the symmetry between greater and lesser, we only have to consider comparisons involving the first element of the two-element list as first comparisons. Comparing the first element of the two-element list with one of the four elements of the other list divides the $15$ possibilities into groups of $10/5$, $6/9$, $3/12$ and $1/14$, respectively. Since there's a group with more than $8$ elements in each case, it's impossible to do the merge with $4$ comparisons in all cases.