Merge two arrays efficiently - one sorted, another unsorted

Problem

Given a sorted array of n elements followed by an unsorted array of length n. Sort the 2 list into one efficiently.

Solution

Method 1 - Insert the elements in sorted array using binary search
Since inserting a single element into array and keeping it sorted is O(n), you cannot get better then that.
Thus, for both cases - sorting the smaller array and then using merge(part1,part2) will be O(n), and thus optimal in terms of asymptotic complexity.

• sorting the smaller array: O(logn*loglog(n)), or O(sqrt(n)*log(sqrt(n)) respectively of the cases.
• merge(part1,part2): O(n+logn) or O(n+sqrt(n)), which is O(n)¹ anyway.

So, the total complexity of both cases is O(n), which is optimal for this problem.




Source

• http://stackoverflow.com/questions/13862701/merge-two-arrays-efficiently-one-sorted-another-unsorted