p3

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#define max 50000

void mergesort(int a[],int low,int high){
    if(low<high){
    int mid;
    mid=(low+high)/2;
    mergesort(a,low,mid);
    mergesort(a,mid+1,high);
    merge(a,low,high,mid);
}
}
void merge(int a[],int low,int high,int mid){
    int b[max],i,j,k;
    i=low;
    j=mid+1;
    k=low;
    while(i<=mid && j<=high)
    {
        if(a[i]<a[j]){
            b[k]=a[i];
            i++;
        }
        else{
            b[k]=a[j];
            j++;
        }
        k++;
    }
    while(i<=mid){
        b[k]=a[i];
        i++;
        k++;
    }
    while(j<=high){
        b[k]=a[j];
        j++;
        k++;
    }
    for(i=low;i<=high;i++){
        a[i]=b[i];
    }
}
int main(){
    int a[max],i,n;
    double runtime=0;
    clock_t start,end;
    printf("enter the value of n:");
    scanf("%d",&n);
    srand(time(NULL));
    for(i=0;i<n;i++){
        a[i]=rand();
    }
    start=clock();
    mergesort(a,0,n-1);
    end=clock();
    runtime=(double)(end-start)/CLOCKS_PER_SEC;
    printf("the sorted elements");
    for(i=0;i<n;i++){
        printf("%d\n",a[i]);
    }
    printf("runtime:%lf",runtime);
    return 0;
}