Merge two sorted arrays (2 solutions) – Code

To merge two sorted arrays in one sorted array, the efficient way is to loop through and compare each element in two arrays, put the smaller one in the result array. Eventually you will get one sorted array.

If you are asked to improve this method, you can do it by merge in space. As initial state, one of the two arrays is defined to have enough space to hold all elements. When merging, you still loop through and compare each element in the arrays. This time, you start from the last elements. 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.

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

Java

Javascript

Python

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:
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.


Download MergeSortedArray.zip
Merge two sorted arrays (YouTube)
Merge sort

Comments are closed