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[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
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 = 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
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!