Merge Sort

http://install4install.com

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

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.

Screen Shot 2014-06-26 at 1.53.09 PM

Fig 1 : Dividing

 

Screen Shot 2014-06-26 at 1.57.46 PM

Fig 2 : Merging

 



Short URL: http://tinyit.cc/d2ed
Author: Cusp2207 on June 26, 2014
Category: Computer Science
Tags:

Leave a Reply

Last articles