Merge sort

Suppose the array A containing  8 elements {5, 2, 4, 7, 1, 3, 2, 6 }.
How it will be sorted see this image.

Merge Sort

download this PPT for all type of sorting : sorting.ppt

Time complexity = Q(n log n)

C program :

 #include<stdio.h>  
 mergesort(int *a,int m,int n)   // merge sort using recursion   
 {   
  int mid;  
   if(m<n)  
   {mid=(n+m)/2;  
   mergesort(a,m,mid);  
   mergesort(a,mid+1,n);  
   merge(a,m,mid,n);}  
 }  
 merge(int *a,int m,int mid,int n)  /*function to merge two sorted arrays  
                      into a sorted array */  
 {int b[40];  
 int i=m,j=mid+1,k=0;  
 while(i<=mid&&j<=n)  
 { if(a[i]>=a[j])  
   b[k++]=a[j++];  
   if(a[i]<=a[j])  
   b[k++]=a[i++];  
 }  
      while(i<=mid)  
      b[k++]=a[i++];  
      while(j<=n)  
   b[k++]=a[j++];  
 i=m;j=0;k--;  
      while(i<=n&&j<=k)  
 a[i++]=b[j++];  
 }  
 main()  
 {  
      int a[50],n,i;  
      printf("\n Enter size of array ");  
      scanf("%d",&n);  
      printf("\n Enter array ");  
      for(i=0;i<n;i++)  
      scanf("%d",&a[i]);  
      mergesort(a,0,n-1);  
      printf("\n Sorted array ");  
      for(i=0;i<n;i++)  
      printf(" %d ",a[i]);  
 }  

OUTPUT :-