Here is the C implementation of Merge Sort.
/*Merge sort*/
#include<stdio.h>
#include<conio.h>
int size;
void main()
{
int i;
int a[50],temp[50];
void mergesort(int[],int[],int,int);
clrscr();
printf("Enter the number of elements:");
scanf("%d",&size);
printf("Enter the elements:\n");
for(i=0;i<size;i++)
{
scanf("%d",&a[i]);
}
mergesort(a,temp,0,size-1);
printf("\nThe sorted elements are:\n");
for(i=0;i<size;i++)
{
printf("%d\t",a[i]);
}
getch();
}
void mergesort(int a[],int temp[],int left,int right)
{
int mid;
void merge(int[],int[],int,int,int);
if(right>left)
{
mid=(left+right)/2;
mergesort(a,temp,left,mid);
mergesort(a,temp,mid+1,right);
merge(a,temp,left,mid+1,right);
}
}
void merge(int a[],int temp[],int left,int mid,int right)
{
int i,left_end,num,pos,m;
left_end=mid-1;
pos=left;
num=right-left+1;
while((left<=left_end)&&(mid<=right))
{
if(a[left]<=a[mid])
{
temp[pos]=a[left];
pos=pos+1;
left=left+1;
}
else
{
temp[pos]=a[mid];
pos=pos+1;
mid=mid+1;
}
}
while(left<=left_end)
{
temp[pos]=a[left];
left=left+1;
pos=pos+1;
}
while(mid<=right)
{
temp[pos]=a[mid];
mid=mid+1;
pos=pos+1;
}
for(i=0;i<=num;i++)
{
a[right]=temp[right];
right=right-1;
}
printf("\n");
for(m=0;m<size;m++)
printf("%d\t",a[m]);
}
