Merge Two Sorted Arrays
Difficulty: Medium
Asked in: Microsoft, Adobe
Understanding The Problem
Problem Description
You are given two sorted arrays
arr1[]
and
arr2[]
of sizes
m
and
n
respectively. Write a program to merge them in such a way that the resultant array is sorted too.
Problem Note:

The size of the resultant array should be
m+n
. 
You are expected to solve this question in
O(m+n)
time. 
Your final array should be the first array i.e. array
arr1[]
.
Example 1
Input: arr1[] = [3, 9, 10, 18, 23], arr2[] = [5, 12, 15, 20, 21, 25]
m = 5, n = 6
Output: [3, 5, 9, 10, 12, 15, 18, 20, 21, 23, 25]
Explanation: The resultant array i.e. arr1[] has all the elements of arr1[] and arr2[], sorted in increasing order. The size of resultant array is m + n = 5 + 6 = 11
Example 2
Input: arr1[] = [2, 5, 9], arr2[] = [12, 19, 23], m = 3, n = 3
Output: [2, 5, 9, 12, 19, 23]
Explanation: The resultant array i.e. arr1[] has all the elements of arr1[] and arr2[], sorted in increasing order. The size of resultant array is m + n = 3 + 3 = 6
Example 3
Input: arr1[] = [2, 20], arr2[] = [5, 9, 14, 16, 19], m = 2, n = 5
Output: [2, 5, 9, 14, 16, 19, 20]
Explanation: The resultant array i.e. arr1[] has all the elements of arr1[] and arr2[], sorted in increasing order. The size of resultant array is m + n = 2 + 5 = 7
Solutions
We will be discussing two different solutions to this problem:
 Merge Function of merge sort : Auxiliary array of n+m size storing values as merge function in merge sort.

Two pointers
: Compare the two values from the end of
ar1
andar2
and store inar1
while decrementing pointers accordingly.
You should try to solve the problem here .
1. Merge Function of Merge Sort
The two given array is sorted, so we can directly use the merge function of merge sort. We create an auxiliary array of size
m+n
and then follow the merge function of the
merge sort
.
Refer to the below example.
Solution Steps

Create an auxiliary array of size
m+ n
where m and n are the sizes ofar1
andar2
respectively. 
While traversing through both the arrays: Pick the smaller of current elements of
arr1
andarr2
, save the smaller value of both the arrays in the auxiliary array, thereby increment the positions accordingly. 
Now copy the auxiliary array to
arr1
as the final array should bearr1
Pseudo Code
void mergeArrays(int arr1[], int arr2[], int n, int m) {
int i = 0, j = 0, k = 0
int[m+n] arr3
// Traverse both array
while (i < n and j < m) {
if (arr1[i] < arr2[j]) {
arr3[k] = arr1[i]
i = i + 1
}
else{
arr3[k] = arr2[j]
j = j + 1
}
k = k + 1
}
while (i < n){
arr3[k] = arr1[i]
i = i + 1
k = k + 1
}
while (j < m){
arr3[k] = arr2[j]
j = j + 1
k = k + 1
}
// copy arr3 to arr1
i = 0
while(i < (m + n)){
arr1[i] = arr3[i]
i = i + 1
}
return arr1
}
Complexity Analysis
Time Complexity: O(n+m)
Space Complexity: O(n+m)
Critical Ideas To Think
 Why did we create an auxiliary array?
 How we are traversing both the array?

On what basis we are storing the value in the auxiliary array from
arr1
andarr2
?
2. Two Pointers
The problem statement requires the output after merge operation in
arr1
. This states that
arr1
has enough space to accommodate the elements of
arr1
and
arr2
.
Now, the two given array are already sorted, so we can put two pointers at the end of each array, say
i
is pointing
arr1[n1]
and
j
is pointing
arr2[m1]
. A third pointer
k
pointing to
arr1[n+m1]
. then we start comparing values at the pointers
i
and
j
, the larger value will be stored at the pointer
k
thereby decreasing the pointer with larger value by 1 and decreasing the pointer
k
by 1. We can continue comparing the values unless
i
and
j
reach to 0th index.
Considering the above Example1:
step 1)
i k
arr1 = [3, 9, 10, 18, 23, _ , _ , _ , _ , _ , _]
j
arr2 = [5, 12, 15, 20, 21, 25]
step 2) arr1[i] < arr2[j] => arr1[k] = arr2[j], j, k
i k
arr1 = [3, 9, 10, 18, 23, _ , _ , _ , _ , _ , 25]
j
arr2 = [5, 12, 15, 20, 21, 25]
step 3) arr1[i] > arr2[j] => arr1[k] = arr1[i], i, k
i k
arr1 = [3, 9, 10, 18, 23, _ , _ , _ , _ , 23 , 25]
j
arr2 = [5, 12, 15, 20, 21, 25]
step 4) arr1[i] < arr2[j] => arr1[k] = arr2[j], j, k
i k
arr1 = [3, 9, 10, 18, 23, _ , _ , _ , 21 , 23 , 25]
j
arr2 = [5, 12, 15, 20, 21, 25]
step 5) arr1[i] < arr2[j] => arr1[k] = arr2[j], j, k
i k
arr1 = [3, 9, 10, 18, 23, _ , _ , 20 , 21 , 23 , 25]
j
arr2 = [5, 12, 15, 20, 21, 25]
.
.
step 10) arr1[i] < arr2[j] => arr1[k] = arr2[j], j, k
i k
arr1 = [3, 5, 9, 10, 12, 15 , 18 , 20 , 21 , 23 , 25]
j
arr2 = [5, 12, 15, 20, 21, 25]
Solution Steps

Create two pointers
i
,j
pointing at arr1[n] and arr2[m] 
While
i ≥ 0
andj ≥ 0,
the pointer with larger value by one and decreasek
by 1. 
Return
arr1
Pseudo Code
void mergeArrays(int arr1[], int arr2[], int n, int m) {
int i = n1
int j = m1
int k = n+m1
// Traverse both array
while (i >= 0 and j >= 0) {
if (arr1[i] > arr2[j]) {
arr1[k] = arr1[i]
i = i  1
}
else{
arr1[k] = arr2[j]
j = j  1
}
k = k  1
}
while (i >= 0){
arr1[k] = arr1[i]
i = i  1
k = k  1
}
while (j >= 0){
arr1[k] = arr2[j]
j = j  1
k = k  1
}
return arr1
}
Complexity Analysis
Time Complexity: O(n+m)
Space Complexity: O(1)
Critical Ideas To Think

Why did we iterate from backward of
arr1
andarr2
?  How different is this approach compared to the merge function of the merge sort?
 Why is the space complexity is O(1)?
Comparison of Different Approaches
Suggested Problems To Solve
 Merge two sorted linked list.
 Merge K sorted arrays.
 Merge two sorted arrays using a heap.
 Merge two unsorted linked list to get a sorted list.
 Merge K sorted arrays of different sizes.
Please comment down below if you have a better insight in the above approach.
Happy Coding, Enjoy Algorithms!