#include<stdio.h>
#include<stdlib.h>
#include<time.h>
void merge(int a[],int l,int m,int r){
int n1=m-l+1,n2=r-m,i,j,k;
int *L=(int*)malloc(n1*sizeof(int));
int *R=(int*)malloc(n2*sizeof(int));
for(i=0;i<n1;i++)
L[i]=a[l+i];
for(j=0;j<n2;j++)
R[j]=a[m+1+j];
i=0;
j=0;
k=l;
while(i<n1&&j<n2)
a[k++]=(L[i]<=R[j])?L[i++]:R[j++];
while(i<n1)
a[k++]=L[i++];
while(j<n2)
a[k++]=R[j++];
free(L);
free(R);
}
void sort(int a[],int l,int r){
if(l<r){
int m=(l+r)/2;
sort(a,l,m);
sort(a,m+1,r);
merge(a,l,m,r);
}
}
int main(){
int n,i;
printf("Enter the number of elements:");
scanf("%d",&n);
if(n<=5000){
printf("Please enter a value greater than 5000");
return 0;
}
int *a=(int*)malloc(n*sizeof(int));
srand(time(NULL));
for(i=0;i<n;i++)
a[i]=rand()%100000;
clock_t s=clock();
for(i=0;i<1000;i++)
sort(a,0,n-1);
clock_t e=clock();
printf("Time taken to sort %d elements: %f seconds\n",n,((double)(e-s))/CLOCKS_PER_SEC/1000);
free(a);
return 0;
}