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.
Leave a Reply