Given are two sorted arrays a, b of type T with size n and m. I am looking for an algorithm that merges the two arrays into a new array (of maximum size n+m).
If you have a cheap comparison operation, this is pretty simple. Just take from the array with the lowest first element until one or both arrays are completely traversed, then add the remaining elements. Something like this http://stackoverflow.com/questions/5958169/how-to-merge-two-sorted-arrays-into-a-sorted-array
However, the situation changes when comparing two elements is much more expensive than copying an element from the source array to the target array. For example you might have an array of large arbitrary precision integers, or strings, where a comparison can be quite expensive. Just assume that creating arrays and copying elements is free, and the only thing that costs is comparing elements.
In this case, you want to merge the two arrays with a minimum number of element comparisons. Here are some examples where you should be able to do much better than the simple merge algorithm:
a = [1,2,3,4, ... 1000]
b = [1001,1002,1003,1004, ... 2000]
Or
a = [1,2,3,4, ... 1000]
b = [0,100,200, ... 1000]
There are some cases where the simple merge algorithm will be optimal, like
a = [1,3,5,7,9,....,999]
b = [2,4,6,8,10,....,1000]
So the algorithm should ideally gracefully degrade and perform a maximum of n+m-1 comparisons in case the arrays are interleaved, or at least not be significantly worse.
One thing that should do pretty well for lists with a large size difference would be to use binary search to insert the elements of the smaller array into the larger array. But that won't degrade gracefully in case both lists are of the same size and interleaved.
Any ideas?
Update for clarification: The only thing available for the elements is a (total) ordering function, so any scheme that makes comparisons cheaper is not possible.
