mergesort.c

merge sort is a sorting algorithm used for sorting data it uses divide and conquer approach

#include<stdio.h>
#include<conio.h>

int *a , n,*result;

void display(int *a , int l,int h)
{
     int i;
     printf("\n\narray is : ");
     for(i=l;i<=h;i++)
          printf(" %d ",a[i]);
}

void merge(int low,int mid,int high)
{
     printf("\nMerge now : low : %d   mid : %d  high  : %d",low,mid,high);
     //display(a,low,mid);
     //display(a,mid+1,high);
     int i=low,j=mid+1,k , count = low;
     while(i<=mid && j <= high)
     {
          if(a[i]>a[j])
              result[count++] = a[j++];
          else
              result[count++] = a[i++];
     }
     //printf("  i= %d  j = %d",i,j);
     while(i<=mid)
     {     
           //printf("in small");
           result[count++] = a[i++];
     }
     while(j<=high)
     {     
           //printf("in large %d count = %d",a[j],count);
           result[count++] = a[j++];
     }
     //printf("\nmerged ");
     //display(result,low,high);
     for(k = low;k<=high;k++)
          a[k] = result[k];
     display(a , low,high);
     //printf("\nmerging ends\n");          
     
}

void mergesort(int low , int high)
{
      int mid;
      //display(a , low,high);
      if(low < high)
      {
             mid = (low + high)/2;
             mergesort(low,mid);
             mergesort(mid+1 , high);
             merge(low,mid,high);
      }
}

int  main()
{
        int i;
        printf("\nEnter no. of elements to sort : ");
        scanf("%d",&n);
        a = (int *)malloc(n*sizeof(int));
        result = (int *)malloc(n*sizeof(int));
        printf("\nEnter the %d elements to be sorted : ",n);
        for(i=0;i<n;i++)
             scanf("%d",&a[i]);
        
        mergesort(0,n-1);
        display(a , 0 , n-1);
        getch();
        return 0;
        
}