## Merge Two Sorted Arrays Difficulty: Medium

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

1. Merge Function of merge sort: Auxiliary array of n+m size storing values as merge function in merge sort.
2. Two pointers: Compare the two values from the end of `ar1` and `ar2` and store in `ar1` 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 of `ar1` and `ar2` respectively.
• While traversing through both the arrays: Pick the smaller of current elements of `arr1` and `arr2`, 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 be `arr1`

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` and `arr2`?

#### 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[n-1]` and `j` is pointing `arr2[m-1]`. A third pointer `k` pointing to `arr1[n+m-1]`. 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` and `j ≥ 0, `the pointer with larger value by one and decrease `k` by 1.
• Return `arr1`

Pseudo Code

``````void mergeArrays(int arr1[], int arr2[], int n, int m) {
int i = n-1
int j = m-1
int k = n+m-1
// 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` and `arr2`?
• 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!