# Merge Two Sorted Arrays

Merge Two Sorted Arrays” is an important problem of array data structure. Here, we are given two sorted arrays of size ‘n’ and ‘m’ respectively. Our task is to write a program to merge these two sorted arrays and the resultant array must itself be sorted array.

Example (Merge Two Sorted Arrays):

```INPUT:
Enter size of first Array: 5
Enter size of second Array: 4
Enter first array elements:
11 33 55 77 99
Enter second array elements:
22 44 66 88
OUTPUT:
The resultant array is:
11 22 33 44 55 66 77 88 99```

There are basically two methods to merge two sorted arrays:

#### METHOD 1: Brute-force Method to Merge Two Sorted Arrays

This is the simplest method to merge two sorted arrays. The steps required are as follows:

1. Scan the size of two arrays as ‘n’ and ‘m’.
2. Scan both the array elements.
3. Create a resultant array res[] of size (n+m).
4. Copy arr1[] elements to res[] from 0 to ‘n-1’ index position. Then, copy arr2[] to res[] array from ‘n’ to ‘m-1’ index position.
5. Sort the resultant array.
6. Print the resultant array.

#### C++ Program to merge two sorted arrays is as follows:

```/* Program to merge two sorted arrays */
#include<bits/stdc++.h>
using namespace std;
int main()
{
/* Scan size of arrays */
int n,m;
cout<<"Enter the size of an arrays: ";
cin>>n>>m;

/* Scan Array Elements */
int arr1[n];
int arr2[m];
cout<<"\nEnter first array elements:\n";
for(int i = 0; i < n; i++)
{
cin>>arr1[i];
}
cout<<"\nEnter second array elements:\n";
for(int i = 0; i < m; i++)
{
cin>> arr2[i];
}

/* Create an array of size (n+m) */
int res[n+m];

/* Copy both the array elements to res[] array */
int pos = 0;
for(int i = 0; i < n; i++)
{
res[pos] = arr1[i];
pos++;
}
for(int i = 0; i < m; i++)
{
res[pos] = arr2[i];
pos++;
}

/* Sort an array */
sort(res,res+(n+m));

/*Printing the result */
cout<<"\nThe resultant array is:\n";
for(int i = 0; i < (n+m); i++)
cout<<res[i]<<" ";
}
```
```OUTPUT:
Enter the size of an arrays: 5 4
Enter first array elements:
11 33 55 77 99
Enter second array elements:
22 44 66 88
The resultant array is:
11 22 33 44 55 66 77 88 99
Time complexity:
O(nlogn), for sorting algoritm complexity.```

#### METHOD 2: Efficient Method To Merge Two Sorted Arrays

The steps required to merge two sorted arrays are as follows:

1. Scan the size of two arrays as ‘n’ and ‘m’.
2. Scan both the array elements.
3. Create an resultant array of size (n+m).
4. Simultaneously iterate over arr1[] and arr2[] and pick the smaller element out of arr1[] or arr2[] and copy it to resultant array at desired location.

#### C++ Program to merge two sorted arrays is as follows:

```/* Program to merge two sorted arrays */
#include<bits/stdc++.h>
using namespace std;
int main()
{
/* Scan size of arrays */
int n,m;
cout<<"Enter the size of an arrays: ";
cin>>n>>m;

/* Scan Array Elements */
int arr1[n];
int arr2[m];
cout<<"\nEnter first array elements:\n";
for(int i = 0; i < n; i++)
{
cin>>arr1[i];
}
cout<<"\nEnter second array elements:\n";
for(int i = 0; i < m; i++)
{
cin>> arr2[i];
}

/* Create an array of size (n+m) */
int res[n+m];

/* Simultaneously copy arr1[] and arr2[] to res[] array */
int pos1 = 0;
int pos2 = 0;
int pos3 = 0;

while(pos1 < n && pos2 < m)
{
/*Copy elements of arr1 */
if(arr1[pos1] < arr2[pos2])
{
res[pos3] = arr1[pos1];
pos1++;
pos3++;
}
/* Copy elements of arr2 */
else if(arr1[pos1] > arr2[pos2])
{
res[pos3] = arr2[pos2];
pos2++;
pos3++;
}
/* Copy both arr1[] and arr2[] element */
else
{
res[pos3] = arr1[pos1];
pos3++;
pos1++;
res[pos3] = arr2[pos2];
pos2++;
pos3++;
}
}

/* Copy remaining element of arr1[] */
while(pos1 < n)
{
res[pos3] = arr1[pos1];
pos1++;
pos3++;
}
/* Copy remaining element of arr2[] */
while(pos2 < n)
{
res[pos3] = arr2[pos2];
pos2++;
pos3++;
}

/*Printing the result */
cout<<"\nThe resultant array is:\n";
for(int i = 0; i < (n+m); i++)
cout<<res[i]<<" ";
}

```
```OUTPUT:
Enter the size of an arrays: 5 4
Enter first array elements:
11 33 55 77 99
Enter second array elements:
22 44 66 88
The resultant array is:
11 22 33 44 55 66 77 88 99
Time complexity:
O(N), here N is (n+m).```

Related Posts: