Merge two sorted arrays (2 solutions) – Code

Merge two sorted arrays is to merge two sorted array in one sorted array. The technique uses while loop to compare the elements in two arrays and put the smaller one in the result array.

How can we improve it? We can improve by merge in space. As initial state, one of the two arrays is defined to have enough space to hold all elements. When merging, we still use a while loop to compare each element in the arrays. This time, we start from the last elements. We put the larger one in the last spot of the output array, then move to the front. Merge in place can improve the space complexity from O(m+n) to (1).

The interviewers are always looking for optimizations in algorithms. Merge sorted arrays is a perfect example. It tests the candidates how to improve the algorithm.

Question: merge two sorted array into one sorted array. How to improve it?

Java Code:

Output:
Array 1: 0 4 5 19 21 33 36 38 61
Array 2: 1 2 7 30 40
Merge (new array): 0 1 2 4 5 7 19 21 30 33 36 38 40 61

Array 1: 0 4 5 19 21 33 36 38 61 0 0 0 0 0
Array 2: 1 2 7 30 40
Merge (in place): 0 1 2 4 5 7 19 21 30 33 36 38 40 61

O Notation:
Solution 1:
Time Complexity : O(m+n), Space Complexity : O(m+n)
Solution 2:
Time Complexity : O(m+n), Space Complexity : O(1)

Note:
If you have any questions or want to put comments, please post at youtube. I will answer you!
The code displayed here is the simplified version after the enhancement in the 2nd edition of Java coding interview pocket book. You can also download the tutorial version by click the top download button.

Actionable:
Download MergeSortedArray.zip
Merge two sorted arrays tutorial
Sort squares with optimization

Comments are closed