Why does merging two sorted arrays take 2N - 1 comparisons?

Question

A friend of mine asked me a question on how to prove that merging two sorted arrays requires at least 2N - 1 comparisons

Prove that merging two sorted arrays of N items requires at least 2N-1 comparisons.

 /*
 * An example program that merges two arrays to prove that merging two
 * sorted arrays takes 2N - 1 comparisons.
 */
public class MergeComparisons 
{
    private int comparisonCounter;
    public MergeComparisons(){
        this.comparisonCounter = 0;
    }
    public int[] merge(int[] a, int[] b) // MERGE TWO ARRAYS
    {
        int[] arr = new int[a.length + b.length];
        int i = 0, j = 0, k = 0;
        while (i < a.length && j < b.length) 
        {
            comparisonCounter++;
            if (a[i] < b[j])
                arr[k++] = a[i++];
            else
                arr[k++] = b[j++];
        }
        while (i < a.length)
            arr[k++] = a[i++];
        while (j < b.length)
            arr[k++] = b[j++];
        return arr;
    }
    public int getComparisons(){
        return comparisonCounter;
    }
    public static void main(String[] args){
        int[] a = {1, 2, 3, 4, 5};
        int[] b = {6, 7, 8, 9, 10};
        MergeComparisons ms = new MergeComparisons();
        //N = 10 because we have 10 elements.
        //Comparisons should be 19.
        int[] merged = ms.merge(a, b);
        System.out.println("After merging two arrays: ");
        for(int i=0; i<merged.length; i++){
            System.out.print(merged[i] + " ");
        }
        System.out.println("\nUsed " + ms.getComparisons() + " comparisons");
    }
}

I wrote the code above to try and test the statement but it does not show. Here is the output

After merging two arrays: 1 2 3 4 5 6 7 8 9 10 Used 5 comparisons

I was assuming it should be at least 9 comparisons from the way the question was posed.

Answer 1

The question asks to show the lower bound on the number of comparisons in merging two sorted arrays of length $N$. Therefore, you need to argue that no matter what comparison-based algorithm you use, it has to make $2N-1$ comparisons, otherwise it would make an error on some input, i.e., it's a worst-case analysis. An algorithm that you come up with might as well do fewer comparisons on some inputs, you just need to show it can't make fewer comparisons on all inputs.

Since we are counting comparisons, I assume we are in a so-called comparison model. Assume your arrays are $A_1 < A_2 < \ldots < A_N$ and $B_1 < B_2 < \ldots < B_N$. Usually proofs in this model are information-theoretic. Imagine your algorithm as a comparison tree, where each node queries $A_i < B_j$ for some indices $i, j \in [N]$. Then each leaf has to correspond to a correct interleaving of the two arrays $A$ and $B$. How many interleavings are possible? Well you need to choose positions for elements of $A$ and fill in the rest with elements of $B$ (elements of $A$ and $B$ have to appear in order, so there is only one way of doing so). This leads to $2N \choose N$ possible interleavings - these should all appear as leaves in your comparison tree. If a tree has $K$ leaves it has depth at least $\log_2 K$ (since it's binary). Unfortunately, using Stirling's approximation it leads to a lower bound of $2N - \frac{1}{2} \log N - 1$, which does not match the upper bound of $2N-1$. This is surprising, because for sorting, the information-theoretic bound is optimal in the comparison model.

Knuth describes an adversarial argument (which he in turn attributes to Graham and Karp) in The Art of Computer Programming, Volume 3. It goes like this. Consider answering a query $A_i < B_j$ as "YES" when $i < j$ and "NO" as $i \ge j$. Then the algorithm will terminate at a leaf $$ B_1 < A_1 < B_2 < A_2 < \cdots < B_N < A_N.$$ Moreover, the algorithm has to make all $2N-1$ comparisons $B_1$ vs $A_1$, $A_1$ vs $B_2$, $B_2$ vs $A_2$, and so on. Why? Suppose it doesn't perform all these comparisons. For instance it does not compare $A_1$ with $B_2$, then the following order is also consistent with our responses: $$ B_1 < B_2 < A_1 < A_2 < B_3 < \cdots < B_N < A_N.$$