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.