#include<stdio.h>
#include<stdlib.h>
void Merge(int a[],int r,int lba,int b[],int s,int lbb,int c[],int lbc)
{
int na=lba,nb=lbb,ptr=lbc,uba=lba+r-1,ubb=lbb+s-1,k;
while(na<=uba && nb<=ubb)
{
if(a[na]<b[nb])
{
c[ptr]=a[na];
ptr=ptr+1;
na=na+1;
}
else
{
c[ptr]=b[nb];
ptr=ptr+1;
nb=nb+1;
}
}
if(na>uba)
{
for(k=0;k<=ubb-nb;k++)
c[ptr+k]=b[nb+k];
}
else
{
for(k=0;k<=uba-na;k++)
c[ptr+k]=a[na+k];
}
return;
}
void MergePass(int a[],int n,int l,int c[])
{
int q,s,r,lb,j;
q=(int)(n/2*l);
s=2*l*q;
r=n-s;
for(j=1;j<=q;j++)
{
lb=(2*j-2)*l;
Merge(a,l,lb,a,l,lb+l,c,lb);
}
if(r<=l)
{
for(j=1;j<=r;j++)
c[s+j]=a[s+j];
}
else
{
Merge(a,l,s+1,a,r,l+s+1,c,s+1);
}
return;
}
void MergeSort(int a[],int n)
{
int l,c[100];
for(l=1;l<n;l=4*l)
{
MergePass(a,n,l,c);
MergePass(c,n,2*l,a);
}
}
main()
{
int i,a[100],n;
printf("Enter the no. of elements\n");
scanf("%d",&n);
printf("Enter the array elements one by one\n");
for(i=0;i<n;i++)
scanf("%d",&a[i]);
MergeSort(a,n);
printf("Array after sorting using MergeSort Procedure\n");
for(i=0;i<n;i++)
printf("%d\t",a[i]);
getch();
}