Facebook

Merge Sort

Merge sort is the divide and conquer method to arrange elements in the order.The steps followed in merge sort are :

  • Divide the sequence of n elements into two sub-sequences of n/2 elements each.
  • Sort the sub-sequences using merge sort.If the size of sequence is 1,nothing more can be done.
  • Merge the sub-sequences to form a sorted sequence of elements.

The complexity of merge sort is O(n log n).It runs faster than insertion and bubble sort but requires large amount of memory.

 

Program

#include<stdio.h>
void merge(int [],int ,int ,int );
void partition(int [],int ,int );
int main()
{
 int a[20];
 int i,size;
 printf("Unsorted List:\t");
 //printf("Enter total no. of elements : ");
 scanf("%d",&size);
 for(i=0; i<size; i++)
 {
   scanf("%d",&a[i]);
   printf("%d\t",a[i]);
 }
 printf("\n");
 partition(a,0,size-1);
 printf("Sorted List  :\t");
 for(i=0; i<size; i++)
 printf("%d \t",a[i]);
 return 0;
}
void partition(int a[],int min,int max)
{
 int mid;
 if(min<max)
 {
   mid=(min+max)/2;
   partition(a,min,mid);
   partition(a,mid+1,max);
   merge(a,min,mid,max);
 }
}
void merge(int a[],int min,int mid,int max)
{
  int temp[20];
  int i,j,k,m; 
  j=min;
  m=mid+1;
  for(i=min; j<=mid && m<=max ; i++)
  {
     if(a[j]<=a[m])
     {
        temp[i]=a[j];
      	j++;
     }
     else
     {
         temp[i]=a[m];
         m++;
     }
  }
  if(j>mid)
  {
     for(k=m; k<=max; k++)
     {
         temp[i]=a[k];
         i++;
     }
  }
  else
  {
     for(k=j; k<=mid; k++)
     {
        temp[i]=a[k];
        i++;
     }
  }
  for(k=min; k<=max; k++)
     a[k]=temp[k];
}

Run

 

 

 

Example

Consider a sequence 7,44,2,10,1,35,74,88,5,3,15.We need to sort this  using merge sort.The list contains 11 elements(Fig 1).Divide the list such that first sub-list has 6 elements and second sub-list has 5 elements(vice-versa is also possible).Keep on dividing till we get single elements in the last.After dividing merge all the elements step by step as shown in Fig 2.

 

 

Rate this post

Comments

So empty here ... leave a comment!

Leave a Reply

Your email address will not be published. Required fields are marked *

Sidebar