C PROGRAM FOR MERGE SORT

/*C PROGRAM FOR MERGE SORT*/

#include<stdio.h>
#include<conio.h>
#define MAX 50
void mergeSort(int arr[],int low,int mid,int high);
void partition(int arr[],int low,int high);

int main()
{
    int merge[MAX],i,n;
     clrscr();
    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]);
    }

    partition(merge,0,n-1);

    printf("After merge sorting elements are: ");
    for(i=0;i<n;i++){
     printf("%d ",merge[i]);
    }
     getch();
   return 0;
}

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:
Enter the total number of elements: 4
Enter the elements which to be sort: 102
450
32
1
After merge sorting elements are: 1 32 102 450 */