Merge Two Sorted Arrays

by · June 14, 2020

“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:

  1. Program to find smallest and largest element of the array.
  2. Program to count occurrences of a particular element in an array.
  3. Program to search an element in an Array (Linear Search).
  4. Program to Rotate Array Elements by ‘D’ positions.
  5. Program to find most frequent element in an array.
  6. Program to find pair in an array with given sum.
  7. Program to find first repeating element of an array.
  8. Program to merge two sorted arrays.
  9. Program to find missing number in an array.
  10. Program to sort if array is sorted.
  11. Program to print Alternate Elements of an Array.
  12. Program to swap kth element from beginning to kth element from end in an Array.
  13. Program to print all possible subarrays of the given array.
  14. Program to print kth smallest and kth largest element of an Array.
  15. Program to find equilibrium index of an Array.
  16. Program to find majority element of an Array.
  17. Program to find mean of the Array.
  18. Program to sort an Array of 0s and 1s.
  19. Program to Count Number of Vowels and Number of Consonants in a String.
  20. Program to Check if String is alphabetic or numeric or alpha-numeric.

Tags:

You may also like...