Sunday, January 19, 2014

Merge two arrays efficiently - one sorted, another unsorted


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


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)1 anyway.
So, the total complexity of both cases is O(n), which is optimal for this problem.




Post a Comment