Time complexity for merging two sorted arrays of size n and m

I was just wondering what is the time complexty of merging two sorted arrays of size n and m, given that n is always greater than m.

I was thinking of using merge sort, which I assume in this case will consume O(log n+m).

I am not really good with big-oh and stuff. Please suggest me the time complexity for this problem and let me know if there is an even optimized way of solving the problem.

Solution

Attention! This answer contains an error

A more efficient algorithm exists and it is presented in another answer.

The complexity is O(m log n).

Let the long array be called a and the short array be b then the algorithm you described can be written as

  for each x in b
      insert x into a

There are m iterations of the loop. Each insertion into a sorted array is an O(log n) operation. Therefore the overall complexity is O (m log n).

Since b is sorted the above algorithm can be made more efficient

  for q from 1 to m
      if q == 1 then insert b[q] into a
      else 
         insert b[q] into a starting from the position of b[q-1]

Can this give better asymptotic complexity? Not really.

Suppose elements from b are evenly spread along a. Then each insertion will take O(log (n/m)) and the overall complexity will be O(m log(n/m) ). If there exists a constant k>1 that does not depend on n or m such that n > k * m then O(log(n/m)) = O(log(n)) and we get the same asymptotic complexity as above.