Merge Sort

 

#include<stdio.h>

#include<unistd.h>

#include<stdlib.h>

#include<malloc.h>

 

 

 

void merge(int *a,int *b,int left,int middle,int right)

{

int i=left,j=middle+1;

int index=left;

while(i<=middle&&j<=right)

if(a[i]<=a[j])

b[index++]=a[i++];

else

b[index++]=a[j++];

while(i<=middle)

b[index++]=a[i++];

while(j<=right)

b[index++]=a[j++];

 

for(i=left;i<=right;i++)

a[i]=b[i];

return;

 

}

 

 

 

void mergesort(int left,int right,int *a,int *b)

{

if(left<right)

{

int middle=(left+right)/2;

mergesort(left,middle,a,b);

mergesort(middle+1,right,a,b);

merge(a,b,left,middle,right);

}

 

 

}

 

 

 

int main()

{

 

 

int *a,n,i;

printf("\n Enter The size of the Data To Sort\n");

scanf("%d",&n);

a=(int *)malloc(sizeof(int)*n);

for(i=0;i<n;i++)

a[i]=rand()%(n+1);

int *b=(int*)malloc(sizeof(int)*n);

struct timeval tv_start,tv_end;

gettimeofday(&tv_start,NULL);

mergesort(0,n-1,a,b);

gettimeofday(&tv_end,NULL);

 

for(i=0;i<n;i++)

printf("%d ",a[i]);

printf("\n---------------------\n Time Taken is %g \n",((tv_end.tv_sec-tv_start.tv_sec)+(tv_end.tv_usec-tv_start.tv_usec)*0.000001));

return 0;

}