Using Auxiliary Space
Approach 1
The idea is based on the approach of combining the two arrays and sorting them.
Algorithm:
 Suppose the size of ‘ARR1’ is ‘M’ and the size of ‘ARR2’ is ‘N’. So, create an array, ‘ARR3’ of size ‘M + N’.
 Copy the elements from ‘ARR1’ to ‘ARR3’.
 Copy the elements from ‘ARR2’ to ‘ARR3’.
 Sort the array, ‘ARR3’.

Copy the first ‘M’ elements from ‘ARR3’ to ‘ARR1’ and copy the remaining ‘N’ elements from ‘ARR3’ to ‘ARR2’.
Let us now see the implementation of the above algorithm.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// Function to merge two sorted arrays.
void mergeSortedArrays(vector<int> &arr1, vector<int> &arr2) {
int m = arr1.size(), n = arr2.size();
// Creating array, 'ARR3' to store elements of 'ARR1' and 'ARR2'.
vector<int> arr3(m + n);
// Copying elements from 'ARR1' to 'ARR3'.
for (int i = 0; i < m; i++) {
arr3[i] = arr1[i];
}
// Copying elements from 'ARR2' to 'ARR3'.
for (int i = 0; i < n; i++) {
arr3[i + m] = arr2[i];
}
// Sorting 'ARR3'.
sort(arr3.begin(), arr3.end());
// Putting elements back into 'ARR1' from 'ARR3'.
for (int i = 0; i < m; i++) { arr1[i] = arr3[i];
}
// Putting elements back into 'ARR2' from 'ARR3'.
for (int i = m; i < m + n; i++) {
arr2[i  m] = arr3[i];
}
}
int main() {
int m, n;
// Taking input for 'ARR1'.
cin >> m;
vector<int> arr1(m);
for (int &element : arr1) {
cin >> element;
}
// Taking input for 'ARR2'.
cin >> n;
vector<int> arr2(n);
for (int &element : arr2) {
cin >> element;
}
// Calling function to merge the arrays, 'ARR1' and 'ARR2'.
mergeSortedArrays(arr1, arr2);
// Printing elements of 'ARR1'.
for (int &element : arr1) {
cout << element << " ";
}
cout << endl;
// Printing elements of 'ARR2'.
for (int &element : arr2) {
cout << element << " ";
}
return 0;
}
Input
5
1 5 7 19 34
7
2 4 8 8 12 17 19
Output
1 2 4 5 7
8 8 12 17 19 19 34
Time Complexity
O((M + N) * log(M + N)), where ‘M’ is the size of the array, ‘ARR1’ and ‘N’ is the size of array ‘ARR2’.
Copying elements from ‘ARR1’ to ‘ARR3’ takes O(M) time.
Copying elements from ‘ARR2’ to ‘ARR3’ takes O(N) time.
Sorting of ‘ARR3’ takes O((M + N) * log(M + N)) time.
Putting elements back into ‘ARR1’ from ‘ARR3’ takes O(M) time.
Putting elements back into ‘ARR2’ from ‘ARR3’ takes O(N) time.
So, the overall time complexity is O(M) + O(N) + O((M + N) * log(M + N)) + O(M) + O(N) = O((M + N) * log(M + N)).
Space Complexity
O(M + N), where ‘M’ is the size of the array, ‘ARR1’ and ‘N’ is the size of array ‘ARR2’.
It is because we have used an additional array, ‘ARR3’ of size ‘M + N’. Hence, the overall space complexity is O(M + N).
Approach 2
Since arrays are already sorted, we can use the merge function of merge sort to optimise the time complexity of Approach 1.
Algorithm:
 Suppose the size of ‘ARR1’ is ‘M’ and the size of ‘ARR2’ is ‘N’. So, create an array, ‘ARR3’ of size ‘M + N’.
 Take three variables: ‘i’, ‘j’ and ‘k’. Initialise all of them by zero. These variables, ‘i’, ‘j’ and ‘k’ will indicate the current index of ‘ARR1’, ‘ARR2’ and ‘ARR3’, respectively.

Run a while loop until we reach the end of either ‘ARR1’ or ‘ARR2’.
 In every iteration, pick the smaller element out of ‘ARR1[ i ]’ and ‘ARR2[ j ]’, and place it in the ‘ARR3[ k ]’.
 Increment the variable ‘k’ and either ‘i’ or ‘j’, depending on the element picked.
 When we run out of elements in either ‘ARR1’ or ‘ARR2’, pick up the remaining elements and put in ‘ARR3’.

Copy the first ‘M’ elements from ‘ARR3’ to ‘ARR1’ and copy the remaining ‘N’ elements from ‘ARR3’ to ‘ARR2’.
The implementation of the above algorithm is shown below:
#include <iostream>
#include <vector>
using namespace std;
// Function to merge two sorted arrays.
void mergeSortedArrays(vector<int> &arr1, vector<int> &arr2) {
int m = arr1.size(), n = arr2.size();
// Creating array, 'ARR3' to store elements of 'ARR1' and 'ARR2'.
vector<int> arr3(m + n);
/*
The variables, 'i', 'j' and 'k' indicates the current index in arrays, 'ARR1', 'ARR2' and 'ARR3', respectively.
*/
int i = 0, j = 0, k = 0;
// Merging arrays, 'ARR1' and 'ARR2' in 'ARR3'.
while (i < m && j < n) {
if (arr1[i] < arr2[j]) {
arr3[k] = arr1[i];
i++;
}
else {
arr3[k] = arr2[j];
j++;
}
k++;
}
// Copying remaining elements of 'ARR1' in 'ARR3'.
while (i < m) {
arr3[k] = arr1[i];
k++, i++;
}
// Copying remaining elements of 'ARR2' in 'ARR3'.
while (j < n) {
arr3[k] = arr2[j];
k++, j++;
}
// Putting elements back into 'ARR1' from 'ARR3'.
for (int i = 0; i < m; i++) {
arr1[i] = arr3[i];
}
// Putting elements back into 'ARR2' from 'ARR3'.
for (int i = m; i < m + n; i++) {
arr2[i  m] = arr3[i];
}
}
int main() {
int m, n;
// Taking input for 'ARR1'.
cin >> m;
vector<int> arr1(m);
for (int &element : arr1) {
cin >> element;
}
// Taking input for 'ARR2'.
cin >> n;
vector<int> arr2(n);
for (int &element : arr2) {
cin >> element;
}
// Calling function to merge the arrays, 'ARR1' and 'ARR2'.
mergeSortedArrays(arr1, arr2);
// Printing elements of 'ARR1'.
for (int &element : arr1) {
cout << element << " ";
}
cout << endl;
// Printing elements of 'ARR2'.
for (int &element : arr2) {
cout << element << " ";
}
return 0;
}
Input
5
1 0 7 18 34
7
0 4 8 9 12 12 18
Output
1 0 0 4 7
8 9 12 12 18 18 34
Time Complexity
O(M + N), where ‘M’ is the size of the array, ‘ARR1’ and ‘N’ is the size of array ‘ARR2’.
Copying elements of ‘ARR1’ and ‘ARR2’ to ‘ARR3’ takes O(M + N) time.
Putting elements back into ‘ARR1’ from ‘ARR3’ takes O(M) time.
Putting elements back into ‘ARR2’ from ‘ARR3’ takes O(N) time.
So, the overall time complexity is O(M + N) + O(M) + O(N) = O(M + N).
Space Complexity
O(M + N), where ‘M’ is the size of the array, ‘ARR1’ and ‘N’ is the size of array ‘ARR2’.
Again, the space complexity is O(M + N) as we have used an additional array, ‘ARR3’ of size ‘M + N’.
Also see, Fibonacci Series in Python
Without Using Auxiliary Space
Approach 1
In this approach, we will compare every element of the array, ‘ARR1’, with the first element of the array, ‘ARR2’. If the element of ‘ARR1’ is greater than the first element of ‘ARR2’, we will swap those elements and sort the array, ‘ARR2’, so that the smallest element is always at the index ‘0’. In this way, we can easily merge the arrays without any extra space.
Algorithm:

Run a loop to traverse the elements of the array, ‘ARR1’.

For every element, ‘element’ in ‘ARR1’. Check whether ‘element’ > ‘ARR2[ 0 ]’.

If yes, swap ‘element’ with ‘ARR2[ 0 ]’ and sort the array, ‘ARR2’.
Let us now see the implementation of the above algorithm.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// Function to merge two sorted arrays.
void mergeSortedArrays(vector<int> &arr1, vector<int> &arr2) {
int m = arr1.size(), n = arr2.size();
// Traversing 'ARR1' and comparing its every element with 'ARR2[0]'.
for (int i = 0; i < m; i++) {
// If 'ARR1[i] > ARR2[0]', swap them and sort 'ARR2'.
if (arr1[i] > arr2[0]) {
swap(arr1[i], arr2[0]);
sort(arr2.begin(), arr2.end());
}
}
}
int main() {
int m, n;
// Taking input for 'ARR1'.
cin >> m;
vector<int> arr1(m);
for (int &element : arr1) {
cin >> element;
}
// Taking input for 'ARR2'.
cin >> n;
vector<int> arr2(n);
for (int &element : arr2) {
cin >> element;
}
// Calling function to merge the arrays, 'ARR1' and 'ARR2'.
mergeSortedArrays(arr1, arr2);
// Printing elements of 'ARR1'.
for (int &element : arr1) {
cout << element << " ";
}
cout << endl;
// Printing elements of 'ARR2'.
for (int &element : arr2) {
cout << element << " ";
}
return 0;
}
Input
7
1 1 2 7 90 899 1000
2
0 0
Output
0 0 1 1 2 7 90
899 1000
Time Complexity
O(M * N * log(N)), where ‘M’ is the size of the array, ‘ARR1’ and ‘N’ is the size of the array ‘ARR2’.
It is because the for loop runs ‘M’ times, and in each iteration, we are sorting the array, ‘ARR2’, depending on the if condition. In the worst case, when every element of ‘ARR1’ is greater than ‘ARR2’, sorting will be performed in every iteration, taking O(N * log (N)) time.
So, the overall time complexity is O(M) * O(N * log(N)) = O(M * N * log(N)).
Space Complexity
O(1).
As no auxiliary space has been used here.
Approach 2
The only goal in Approach 1 is to place the swapped element in ‘ARR2′ at the correct position after swapping the elements. In such a situation, sorting the entire array is unnecessary. We can use the insertion sort algorithm to shift the elements and place the swapped element at the correct position.
Algorithm:

Run a loop to traverse the elements of the array, ‘ARR1’.

For every element, ‘element’ in ‘ARR1’. Check whether ‘element’ > ‘ARR2[ 0 ]’.
 If yes, swap ‘element’ with ‘ARR2[ 0 ]’.

To sort the array, ‘ARR2’, store the first element in a variable, ‘K’ and then run a loop to left shift all the elements smaller than ‘K’. In the end, put the element ‘K’ at the correct position in the array.
The implementation of the above algorithms is provided below.
#include <iostream>
#include <vector>
using namespace std;
// Function to merge two sorted arrays.
void mergeSortedArrays(vector<int> &arr1, vector<int> &arr2) {
int m = arr1.size(), n = arr2.size();
// Traversing 'ARR1' and comparing its every element with 'ARR2[0]'.
for (int i = 0; i < m; i++) {
// If 'ARR1[i] > ARR2[0]', swap them and sort 'ARR2'.
if (arr1[i] > arr2[0]) {
swap(arr1[i], arr2[0]);
int k = arr2[0], j;
// Shifting elements of the array, 'ARR2' to place 'ARR2[0]' at correct position.
for (j = 1; j < n; j++) {
if (arr2[j] < k) {
arr2[j1] = arr2[j];
}
else {
break;
}
}
arr2[j  1] = k;
}
}
}
int main() {
int m, n;
// Taking input for 'ARR1'.
cin >> m;
vector<int> arr1(m);
for (int &element : arr1) {
cin >> element;
}
// Taking input for 'ARR2'.
cin >> n;
vector<int> arr2(n);
for (int &element : arr2) {
cin >> element;
}
// Calling function to merge the arrays, 'ARR1' and 'ARR2'.
mergeSortedArrays(arr1, arr2);
// Printing elements of 'ARR1'.
for (int &element : arr1) {
cout << element << " ";
}
cout << endl;
// Printing elements of 'ARR2'.
for (int &element : arr2) {
cout << element << " ";
}
return 0;
}
Input
7
1 1 2 7 90 899 1000
2
0 0
Output
0 0 1 1 2 7 90
899 1000
Time Complexity
O(M * N), where ‘M’ is the size of the array, ‘ARR1’ and ‘N’ is the size of the array ‘ARR2’.
It is because the for loop runs ‘M’ times, and in each iteration, we are shifting the elements of the array, ‘ARR2’, depending on the if condition. In the worst case, when all the elements of ‘ARR1’ will be greater than all the elements of ‘ARR2’, shifting will be performed in every iteration for all the elements of ‘ARR2’, which will take O(N) time.
So, the overall time complexity is O(M) * O(N) = O(M * N).
Space Complexity
O(1).
As no auxiliary space has been used here.
Approach 3
Suppose there are ‘M’ elements in ‘ARR1’ and ‘N’ elements in ‘ARR2’. We will modify the arrays, ‘ARR1’ and ‘ARR2’ so that out of these ‘M + N’ elements, the first ‘M’ smaller elements are kept in ‘ARR1’ and the next ‘N’ elements are kept in ‘ARR2’. We will not maintain the sorted order while segregating the elements.
When elements are successfully segregated, we can sort both of these arrays to obtain the desired result.
Algorithm:
 Store size of ‘ARR1’ and ‘ARR2’ in variables ‘M’ and ‘N’, respectively.
 Take two variables, ‘i’ and ‘j’ and initialise them with zero.

Run a while loop till i < M and j < N.
 If ARR1[ i ] < ARR2[ j ] that shows the ‘i’th element in ‘ARR1’ is smaller than ‘j’th element in ‘ARR2’. Since we have to keep first ‘M’ smaller elements in ‘ARR1’. We will simply increment the variable ‘i’.
 Else, we will swap the element ‘ARR2[ j ]’ with the element ‘ARR1[ M – 1 ]’. Then, decrement ‘M’ and increment ‘j’.

At this point, we will be having the first ‘M’ smaller elements in ‘ARR1’ and the next ‘N’ elements in ‘ARR2’. So now sort the arrays, ‘ARR1’ and ‘ARR2’.
The implementation of the above algorithm is provided below:
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// Function to merge two sorted arrays.
void mergeSortedArrays(vector<int> &arr1, vector<int> &arr2) {
int m = arr1.size(), n = arr2.size();
int i = 0, j = 0;
// Segregating elements.
while (i < m && j < n) {
if (arr1[i] < arr2[j])
i++;
else {
swap(arr1[m  1], arr2[j]);
m, j++;
}
}
// Sorting array, 'ARR1'.
sort(arr1.begin(), arr1.end());
// Sorting array, 'ARR2'.
sort(arr2.begin(), arr2.end());
}
int main() {
int m, n;
// Taking input for 'ARR1'.
cin >> m;
vector<int> arr1(m);
for (int &element : arr1) {
cin >> element;
}
// Taking input for 'ARR2'.
cin >> n;
vector<int> arr2(n);
for (int &element : arr2) {
cin >> element;
}
// Calling function to merge the arrays, 'ARR1' and 'ARR2'.
mergeSortedArrays(arr1, arr2);
// Printing elements of 'ARR1'.
for (int &element : arr1) {
cout << element << " ";
}
cout << endl;
// Printing elements of 'ARR2'.
for (int &element : arr2) {
cout << element << " ";
}
return 0;
}
Input
4
3 1 5 8
7
2 1 0 1 3 5 7
Output
3 2 1 1
0 1 3 5 5 7 8
Time Complexity
O(M * log(M) + N * log(M)), where ‘M’ is the size of the array, ‘ARR1’ and ‘N’ is the size of the array ‘ARR2’.
Segregation of elements of takes O(max(M, N)) time.
Sorting array, ‘ARR1’ takes O(M * log(M)) time.
Sorting array, ‘ARR2’ takes O(N * log(N)) time.
So, the overall time complexity is O(max(M, N)) + O(M * log(M)) + O(N * log(N)) = O(M * log(M) + N * log(M)).
Space Complexity
O(1).
As no auxiliary space has been used here.
Approach 4 (For NonNegative Integers)
In this approach, we will again use the merge function of the merge sort to merge the arrays, ‘ARR1’ and ‘ARR2’. In the usual merge function, we use an auxiliary array to maintain the merged elements in a sorted manner. To achieve the same without any extra space, we will store the new and old values in the same location by using division and modulus operators. Let us see how.
Suppose we have an integer variable, ‘VAR’, containing an integer ‘X’. Now, we also want to store an integer, ‘Y’ in ‘VAR’ so, if we change VAR = X to VAR = X + Y * N, where ‘N’ is an integer greater than both ‘X’ and ‘Y’.
In that case, VAR / N = Y and VAR % N = X.
So, the old value ‘X’ and the new value ‘Y’ are now contained by the same variable ‘VAR’.
The implementation of the above approach is provided below:
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// Function to merge two sorted arrays.
void mergeSortedArrays(vector<int> &arr1, vector<int> &arr2) {
int m = arr1.size(), n = arr2.size();
// 'MAXN' will store the value greater than all the elements of 'ARR1' and 'ARR2'.
int maxN = max(*max_element(arr1.begin(), arr1.end()), *max_element(arr2.begin(), arr2.end()));
// Incrementing 'MAXN' by 1 to avoid collision in modulo operation.
maxN++;
int i = 0, j = 0, k = 0;
while (i < m && j < n && k < (m + n)) {
// Extracting the old values.
int element1 = arr1[i] % maxN;
int element2 = arr2[j] % maxN;
if (element1 <= element2) {
// Updating element with new value.
if (k < m) {
arr1[k] += (element1 * maxN);
}
else {
arr2[k  m] += (element1 * maxN);
}
i++, k++;
}
else {
// Updating element with new value.
if (k < m) {
arr1[k] += (element2 * maxN);
}
else {
arr2[k  m] += (element2 * maxN);
}
j++, k++;
}
}
// Processing remaining elements of 'ARR1'.
while (i < m) {
int element = arr1[i] % maxN;
if (k < m) {
arr1[k] += (element * maxN);
}
else {
arr2[k  m] += (element * maxN);
}
i++, k++;
}
// Processing remaining elements of 'ARR2'.
while (j < n) {
int element = arr2[j] % maxN;
if (k < m) {
arr1[k] += (element * maxN);
}
else {
arr2[k  m] += (element * maxN);
}
j++, k++;
}
// Updating 'ARR1' elements with new values.
for (int i = 0; i < m; i++) {
arr1[i] = arr1[i] / maxN;
}
// Updating 'ARR2' elements with new values.
for (int i = 0; i < n; i++) {
arr2[i] = arr2[i] / maxN;
}
}
int main() {
int m, n;
// Taking input for 'ARR1'.
cin >> m;
vector<int> arr1(m);
for (int &element : arr1) {
cin >> element;
}
// Taking input for 'ARR2'.
cin >> n;
vector<int> arr2(n);
for (int &element : arr2) {
cin >> element;
}
// Calling function to merge the arrays, 'ARR1' and 'ARR2'.
mergeSortedArrays(arr1, arr2);
// Printing elements of 'ARR1'.
for (int &element : arr1) {
cout << element << " ";
}
cout << endl;
// Printing elements of 'ARR2'.
for (int &element : arr2) {
cout << element << " ";
}
return 0
Input
4
1 3 5 8
7
0 1 3 5 7 8 11
Output
0 1 1 3
3 5 5 7 8 8 11
Time Complexity
O(M + N), where ‘M’ is the size of the array, ‘ARR1’ and ‘N’ is the size of the array ‘ARR2’.
Merging elements of ‘ARR1’ and ‘ARR2’ in ‘ARR3’ takes O(M + N) time.
Updating ‘ARR1’ elements with new values takes O(M) time.
Updating ‘ARR2’ elements with new values takes O(N) time.
So, the overall time complexity is O(M + N) + O(M) + O(N) = O(M + N).
Space Complexity
O(1).
As no auxiliary space has been used here.
Check out this array problem  Merge 2 Sorted Arrays
Refer to know about : Topological sort
Frequently Asked Questions
What is merge sorted array?
Merging a sorted array refers to the process of combining two or more sorted arrays into a single sorted array, maintaining the order of elements. This operation is common in algorithms and data structures for tasks like merging data from multiple sources or combining sorted lists.
How do we merge 2 arrays into single array?
To merge two arrays into a single sorted array, initialize a new array, and then iterate through both input arrays simultaneously, comparing elements and adding the smaller one to the new array. Continue until both input arrays are fully processed.
How to merge two sorted arrays in C?
To merge two sorted arrays in C, create a new array with sufficient space, then iterate through both arrays, comparing elements, and copying the smaller one into the new array. Continue until both input arrays are fully processed, resulting in a merged sorted array.
How do I merge two sorted arrays with two pointers?
Merge two sorted arrays using two pointers in C by initializing two pointers for each array, comparing elements at those pointers, and copying the smaller one into a new array. Move the respective pointer forward and repeat until both arrays are fully merged.
Conclusion
With this discussion, this blog attempted to break down the famous interview problem, merge two sorted arrays. We discussed different approaches and their time and space complexity. Now, next time someone asks you to merge two sorted arrays without extra space, you are going to shine!
Recommended problems 
Also Read  Selection Sort in C, Array in Javascript, Array in Python
Consider checking out the Guided Path of Data Structures and Algorithms to learn more useful concepts. Also, head over right now to Coding Ninjas Studio to practice similar problems and crack your interviews like a Ninja!
We hope you found this blog useful. Feel free to let us know your thoughts in the comments section.