Merge two sorted arrays (2 solutions) – Code

To merge two sorted arrays in one sorted array, you can loop through the elements of both arrays and compare them. Put the smaller one in the output array. When one array reaches the end, move the rest of elements of the other array into the output array.

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

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)

How to merge two sorted arrays in O(1) space?

In merge inspace, you declare one of the array to have enough space to hold the elements in the other array. When merging, you start from the last elements of the arrays and compare them. Put the larger one in the last spot of the output array, then move to the front. Since you don’t need extra memory space, merge in place can improve the space complexity from O(m+n) to O(1).