Merging Two Sorted Arrays with O(log(n+m)) Worst Case

Question

What kind of algorithm can I use to merge two sorted arrays into one sorted array with worst-case time complexity of O(log(m+n)) where n, m are the length of the arrays? I have very little experience with algorithms, but I checked out merge-sort and it seems that the time-complexity for the merging step is O(n). Is there a different approach to merge in O(log(n))?

Edit: I hadn't considered initially, but maybe it's not possible to merge two sorted arrays in O(log(n))? The actual goal is to find the median of two sorted arrays. Is there a way to do this without merging them?

The only idea I've had was I read that merging two binomial heaps is O(log(n)), but turning an array into a binomial heap is O(n) I think so that won't work.

Edit2: I'm going to post a new question because I've realized that merging will never work fast enough. I think instead I need to perform a binary search on each array to find the median in log(n).

Answer 1

I don't think there is an algorithm that would merge two arrays in O(log(n+m)) time.

And it makes sense when you think about it. If you're trying to create a new sorted array of n+m elements you will need to do at least n+m copies. There is no way getting around that.

I think the best way would be to iterate through each array simultaneously and, at each iteration, compare the values of both elements. If one is less than the other (if you want the array sorted in descending order), then copy that element to the array and increment your indexing pointer for that array and vice versa. If the two elements are the same, you can just add them both into the newly sorted array and increment both pointers.

Continue until one of the pointers has reached the end of its respective array and then copy in the rest of the other array once one has.

That should be O(m+n)

Regarding your edit, there is a way to find the median of two separate arrays in log(n + m) time.

You can first find the median of the two sorted arrays (the middle element) and compare them. If they are equal, then that is the median. If the first's median is greater than the second's you know the median has to be in either the first half of the first array or the second half of the second array and vice versa if the first's median is less than the second's.

This method cuts your search space in half each iteration and is thus log(n + m)

Answer 2

You need to merge the arrays. so, no matter what, you need to traverse the 2 arrays at least, so the complexity can't be less than o(m+n)

Answer 3

You're probably thinking of The Selection Algorithm.

For a sorted data structure, finding the median is O(1). For an unsorted data structure (or a data structure where the data is sorted into two logical partitions) the runtime is O(n).

You could probably pull it off with a massively parallel reduction algorithm, but I think that's cheating in Runtime Analysis terms.

So I don't believe there's an algorithm that reduces it below O(n) (or, in your case, O(n+m))