Merge two sorted arrays in C++

This article will guide you on how to write an efficient program to merge two sorted arrays in C++. To understand better, let us see some examples.If the input arrays are :

a[ ]={10,15,20,40}

b[ ]={5,6,6,10,15},then the output should be:

Output:5 6 6 10 10 15 15 20 40

The output should be in sorted order.

We will first discuss the naive solution to solve the problem. In this approach, we create an array c of size m+n (c[m+n]) where m is the size of a[ ] and n is the size of b[ ]. We copy all the elements of the array a[ ] to array c[ ] and then copy all the elements of the array b[ ] to array c[ ].If we consider the above example :

a[4 ]={10,15,20,40}

b[5]={5,6,6,10,15},then the array c will be:

c[9]={10,15,20,40,5,6,6,10,15}.

Now we sort the array c [] and print the elements.

c[9]={5,6,6,10,10,15,15,20,40}

C++ program to merge two sorted arrays

Below is the C++ code to perform our task:

#include <bits/stdc++.h>
using namespace std;
void merge(int a[],int b[],int m,int n)
{
  int c[m+n];
  for(int i=0;i<m;i++)
  {
    c[i]=a[i];
  }
  for(int j=0;j<n;j++)
  {
    c[j+m]=b[j];
  }
  sort(c,c+m+n);
  for(int i=0;i<m+n;i++)
  {
    cout<<c[i]<<" ";
  }
}
int main()
{
   int a[] = {10,15,20,40}; 
    int m = sizeof(a) / sizeof(a[0]); 
  
    int b[] = {5,6,6,10,15}; 
    int n = sizeof(b) / sizeof(b[0]); 
  
    
    merge(a, b, m, n);
}

Output:

5 6 6 10 10 15 15 20 40

Time Complexity of the above solution is:0((m+n)*log(m+n))

Alternative Method:

In this method, we use the idea of merge sort. We traverse both the arrays a[ ] and b[ ] simultaneously. We start from the first element in both the arrays and compare the first element in array a[ ] with the first element in array b[ ] and the print the smaller of the two elements and move one position ahead in that array and continue the same process with the other elements.

Below is the required C++ code:

#include <bits/stdc++.h>
using namespace std;
void merge(int a[],int b[],int m,int n)
{
  int i=0,j=0;
  while(i<m && j<n)
  {
    if(a[i]<b[j]){
      cout<<a[i++]<<" ";
    }
    else
    {
      cout<<b[j++]<<" ";
    }
  }
    while(i<m)
    {
      cout<<a[i++]<<" ";
    }
    while(j<n)
    {
      cout<<b[j++]<<" ";
    }
  
}
int main()
{
   int a[] = {10,15,20,40}; 
    int m = sizeof(a) / sizeof(a[0]); 
  
    int b[] = {5,6,6,10,15}; 
    int n = sizeof(b) / sizeof(b[0]); 
  
    
    merge(a, b, m, n);
}

Output:

5 6 6 10 10 15 15 20 40

Time Complexity:0(m+n)

Thank you for reading. I hope this helps.