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

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!**