19785

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

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

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)`

<strong>Regarding your edit</strong>, 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)`

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)