// Program to implement Merge sort
#include<iostream.h>
#include<iomanip.h>
#include<conio.h>
class mergesort
{
private:
int *x,*y,*z;
int items1,items2;
public:
mergesort(int,int);
~mergesort();
void input1(int []);
void input2(int []);
void msort(int [], int);
void display();
void sort();
};
mergesort::mergesort(int p,int q)
{
items1=p;
items2=q;
x=new int[items1];
y=new int[items2];
z=new int[items1+items2];
}
mergesort::~mergesort()
{
delete [] x;
delete [] y;
delete [] z;
}
void mergesort::input1(int a[])
{
for(int i=0;i<items1;i++)
x[i]=a[i];
msort(x,items1);
cout<<"\n Sorted first array :";
for(i=0;i<items1;i++)
cout<<setw(5)<<x[i];
}
void mergesort::input2(int b[])
{
for(int i=0;i<items2;i++)
y[i]=b[i];
msort(y,items2);
cout<<"\n Sorted second array : ";
for(i=0;i<items2;i++)
cout<<setw(5)<<y[i];
}
void mergesort::msort(int m[],int n)
{
int swap=1;
for(int i=0;i<n && swap==1;i++)
{
swap=0;
for(int j=0;j<n-(i+1);j++)
{
if(m[j]>m[j+1])
{
int temp;
temp=m[j];
m[j]=m[j+1];
m[j+1]=temp;
swap=1;
}
}
}
}
void mergesort::display()
{
cout<<"\n Sorted elements are :";
for(int i=0;i<items1+items2;i++)
cout<<setw(5)<<z[i];
}
void mergesort::sort()
{
int i,j,k;
i=j=k=0;
while((i<items1) && (j<items2))
{
if(x[i]<y[j])
{
z[k]=x[i];
i++;
k++;
}
else
{
if(x[i]>y[j])
{
z[k]=y[j];
j++;
k++;
}
else
{
z[k]=x[i];
i++;
j++;
k++;
}
}
}
while(i<items1)
{
z[k]=x[i];
i++;
k++;
}
while(j<items2)
{
z[k]=y[j];
j++;
k++;
}
}
int main()
{
int elements1[100],elements2[100],n1,n2;
clrscr();
cout<<"Enter number of elements for first array \n";
cin>>n1;
cout<<"Enter"<<n1<<"elements \n";
for(int i=0;i<n1;i++)
cin>>elements1[i];
cout<<"Enter number of elements for second array \n";
cin>>n2;
cout<<"Enter"<<n2<<"elements \n";
for(i=0;i<n2;i++)
cin>>elements2[i];
mergesort obj(n1,n2);
obj.input1(elements1);
obj.input2(elements2);
obj.sort();
obj.display();
return 0;
}
Test data
Enter number of elements for first array
5
Enter 5 elements
20 10 30 5 4
Enter number of elements for second array
4
Enter 4 elements
9 8 7 6
Output
Sorted first array : 4 5 10 20 30
Sorted second array : 6 7 8 9
Sorted elements are : 4 5 6 7 8 9 10 20 30