6
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Maybe it was meant to be "at most"? Have you tried two comb-like arrays? [1,3,5,7,9],[2,4,6,8,10]? $\endgroup$ – Evil May 22 '16 at 1:15
  • 2
    $\begingroup$ Please get rid of the source code and replace it with ideas, pseudo code and arguments of correctness. See here and here for related meta discussions. $\endgroup$ – Raphael May 22 '16 at 2:23
  • 3
    $\begingroup$ You are friends with your teacher? ;) $\endgroup$ – Raphael May 22 '16 at 2:23
  • 1
    $\begingroup$ What does the question mean exactly? I interpret it as "for any correct merging algorithm and any n, there exists an input of size n where the algorithm makes at least 2n-1 comparisons." $\endgroup$ – usul May 22 '16 at 2:28
8
$\begingroup$

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.$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.