Programming Treasure

Merge Sort 

 It is one of the stable sort working on Divide and Conquer Principle. Primarily it keeps  dividing the array  into two parts(approximately) recursively till we find the sub arrays with one element each. Then we start merging the sub-arrays having single elements into an array of two and then these will merged into an array four...like wise we continue merging upwards and finally merge them into single array, and find this arrays as a sorted array. The following image illustrates the concept of partitioning and merging. The worst case complexity of this algorithm is  O(nlog₂n)

 

 

C program to perform merge sort:

#include<stdio.h>
#include<stdlib.h>

void part(int*,int,int);
void merge(int*,int,int,int);

main()
{
 int a[100],i,n;

 printf("Enter no.of elements\n");
 scanf("%d",&n);

 printf("Enter %d items\n",n);
 for(i=0;i<n;i++)
  scanf("%d",&a[i]);

 part(a,0,n-1);

 for(i=0;i<n;i++)
  printf("%d\n",a[i]);


}
void part(int *a,int l,int h)
{
 int m;
 if(l<h)
 {
  m=(l+h)/2;
  part(a,l,m);
  part(a,m+1,h);
  merge(a,l,m,h);
 }

}

void merge(int *a,int l,int m,int h)
{
 int i,j,k,temp[100];
 i=l;j=m+1;k=l;

 while(i<=m&&j<=h)
 {
  if(a[i]<a[j])
  {
  temp[k]=a[i];
  i++;
  k++;
  }
  else
  {
  temp[k]=a[j];
  j++;
  k++;
  }


 }
 while(i<=m)
 {
  temp[k]=a[i];
  i++;
  k++;
 }
 while(j<=h)
 {
  temp[k]=a[j];
  j++;
  k++;
  }

 for(i=l;i<=h;i++)
 a[i]=temp[i];

}
/* output


Enter no.of elements
5                                                                              
Enter 5 items                                                                  
0                                                                              
3669                                                                           
4                                                                              
52                                                                             
14                                                                             
0                                                                              
4                                                                              
14                                                                             
52                                                                             
3669
*/