Given two sorted arrays arr1
and arr2
, merge them together and return the new array.
This is a prerequisite to MergeSort.
Example:
One idea is to simply concatenate the arrays and call sort. That's an O(nlogn) time complexity algorithm. It turns out we can do much better than that. An indication we can do better is that the concatenate algorithm doesn't take advantage of the fact that the arrays are sorted at all.
The idea to solving this problem is to start with a blank array, and add elements in increasing order.
The trick to doing this is that the smallest value is guaranteed to be the leftmost element in one of the arrays, because they're sorted. We can take whatever leftmost element is smaller, and add it to our solution.
We can keep repeating this, comparing the leftmost values in the two arrays, and adding whatever is smaller to our solution.
Here's the code:
Time Complexity O(n), where n is the total number of elements.
Space Complexity O(n) to store the merged array.