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

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 88INPUT:The resultant array is: 11 22 33 44 55 66 77 88 99OUTPUT:

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:

- Scan the size of two arrays as ‘n’ and ‘m’.
- Scan both the array elements.
- Create a resultant array res[] of size (n+m).
- 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.
- Sort the resultant array.
- 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]<<" ";
}
```

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 99OUTPUT:O(nlogn), for sorting algoritm complexity.Time complexity:

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

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

- Scan the size of two arrays as ‘n’ and ‘m’.
- Scan both the array elements.
- Create an resultant array of size (n+m).
- 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]<<" ";
}
```

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 99OUTPUT:O(N), here N is (n+m).Time complexity:

**Related Posts:**

- Program to find smallest and largest element of the array.
- Program to count occurrences of a particular element in an array.
- Program to search an element in an Array (Linear Search).
- Program to Rotate Array Elements by ‘D’ positions.
- Program to find most frequent element in an array.
- Program to find pair in an array with given sum.
- Program to find first repeating element of an array.
- Program to merge two sorted arrays.
- Program to find missing number in an array.
- Program to sort if array is sorted.
- Program to print Alternate Elements of an Array.
- Program to swap kth element from beginning to kth element from end in an Array.
- Program to print all possible subarrays of the given array.
- Program to print kth smallest and kth largest element of an Array.
- Program to find equilibrium index of an Array.
- Program to find majority element of an Array.
- Program to find mean of the Array.
- Program to sort an Array of 0s and 1s.
- Program to Count Number of Vowels and Number of Consonants in a String.
- Program to Check if String is alphabetic or numeric or alpha-numeric.