0

I was doing some algorithm things. There are two arrays, array A with length n has been sorted in ascending order while array B with length m is not. The question asks us to produce an array where m+n integers are sorted in ascending order. And it should terminates in o(n+mlogm) time. What I think is to perform merge sort on B first and it may take o(mlogm) time. Then perform merge sort on A and B but clearly it takes more time. Are there any other solution?

Haylee
  • 1
  • 1
    Possible duplicate of [Merge two arrays efficiently - one sorted, another unsorted](http://stackoverflow.com/questions/13862701/merge-two-arrays-efficiently-one-sorted-another-unsorted) – Saurav Sahu Nov 02 '16 at 11:52

1 Answers1

1

You are right that the first step is sorting of the second array in O(mlogm).

But the second step is simple merging of sorted arrays that takes O(n + m)

(merging is equal to Merge phase of mergesort. Arbitrary example)

So overall complexity is O(mlogm + m + n) = O(mlogm + n)

Community
  • 1
  • 1
MBo
  • 77,366
  • 5
  • 53
  • 86