# 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,6,6,10,15},then the array c will be:

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

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

c={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);

int b[] = {5,6,6,10,15};
int n = sizeof(b) / sizeof(b);

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);

int b[] = {5,6,6,10,15};
int n = sizeof(b) / sizeof(b);

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.