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