C program to implement Merge Sort

There  is a C program to implement Merge Sort is given below. Merge sort is based on the divide conquer strategy. Array is divided in to two halves.if the array length is n, then it is divided into n/2,n/4,n/8…. and each part is sorted independently, then conquered into the sorted array. The efficiency of merge sort is O(n log n).

The program which is written bellow also compute the time complexity of sorting.

Example of C program to implement Merge Sort 

#include<stdio.h>
#include<conio.h>
#include<time.h>
#define MAX 50

void mergeSort(int arr[],int low,int mid,int high);
void partition(int arr[],int low,int high);

void main(){
   
    int merge[MAX],i,n;
 clock_t top, bottom;
    printf("Enter the total number of elements: ");
    scanf("%d",&n);

    printf("Enter the elements which to be sort: ");
    for(i=0;i<n;i++){
         scanf("%d",&merge[i]);
    }
 top = clock();
    partition(merge,0,n-1);
 delay(100);
 bottom = clock();
    printf("After merge sorting elements are: ");
    for(i=0;i<n;i++){
         printf("%d ",merge[i]);
    }
 printf("nnThe time complexity is : %f", (bottom-top)/CLK_TCK);
 getch();
}

void partition(int arr[],int low,int high){

    int mid;

    if(low<high){
         mid=(low+high)/2;
         partition(arr,low,mid);
         partition(arr,mid+1,high);
         mergeSort(arr,low,mid,high);
    }
}

void mergeSort(int arr[],int low,int mid,int high){

    int i,m,k,l,temp[MAX];

    l=low;
    i=low;
    m=mid+1;

    while((l<=mid)&&(m<=high)){

         if(arr[l]<=arr[m]){
             temp[i]=arr[l];
             l++;
         }
         else{
             temp[i]=arr[m];
             m++;
         }
         i++;
    }

    if(l>mid){
         for(k=m;k<=high;k++){
             temp[i]=arr[k];
             i++;
         }
    }
    else{
         for(k=l;k<=mid;k++){
             temp[i]=arr[k];
             i++;
         }
    }
   
    for(k=low;k<=high;k++){
         arr[k]=temp[k];
    }
}


Output