MERGE SORT USING C PROGRAM

Aim: Merge Sort Using C program

Program:

#include<stdio.h>

void main()

{

 int i,a[50],n;

 clrscr();

 printf(" Enter no of elements to be entered");

 scanf("%d",&n);

 printf(" Enter elements");

 for(i=1;i<=n;i++)

  scanf("%d",&a[i]);

 mergesort(a,1,n);

 printf(" Merge sort=");

 for(i=1;i<=n;i++)

  printf("%d ",a[i]);

 getch();

}

int mergesort(int a[],int low,int high)

{

 int mid;

 if(low<high)

 {

  mid=(low+high)/2;

  mergesort(a,low,mid);

  mergesort(a,mid+1,high);

  merge(a,low,mid,high);

 }

 return;

}

int merge(int a[],int low,int mid,int high)

{

 int i,j,k,l,b[50];

 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++;

 }

 if(i>mid)

 {

  for(l=j;l<=high;l++)

  {

   b[k]=a[l];

   k++;

  }

 }

 else

 {

  for(l=i;l<=mid;l++)

  {

   b[k]=a[l];

   k++;

  }

  for(l=low;l<=high;l++)

  {

   a[l]=b[l];

  }

 }

}

Merge Sort:

Merge sort is an algorithm that has a fairly efficient space time complexity -

O(n log n) and is fairly trivial to implement. The algorithm is based on splitting

a list, into two similar sized lists (left, and right) and sorting each list and then

merging the sorted lists back together.

Note: the function MergeOrdered simply takes two ordered lists and makes

them one.

Output: