Merge sort

                                             

Definiton:   Merge Sort is a type of Divide and Conquer Method.
    It is one of the most popular sorting algorithms which call recursive algorithms.
In this sorting, we divide the array recursively in two halves, until each sub-array contains a single element, and
then we merge the sub-array in a way that it results into a sorted array.


*** Merge sort having two functions a)Mergesort()  function which can divide the array into the sub-array,
  b)Merge()  function which can merge two sub-array in a way that it results into a sorted array.


Algorithm for Merge sort:

a) For Divide the Array:
   void merge_sort (int A[ ] , int low , int high ):
    {
               if( low < high )
{
             int mid = (low + high ) / 2 ;           // defines the current array in 2 parts .
               merge_sort (A, low , mid ) ;                 // sort the 1st part of array .
               merge_sort (A,mid+1 , high ) ;              // sort the 2nd part of array.

         // merge the both parts by comparing elements of both the parts.
          merge(A,low , mid , high ); 
    }                   
}

b) For Merge the Sub-Array:

void merge(int A[ ] , int low, int mid, int high):
{
  //stores the starting position of both parts in temporary variables.
    int p = low ,q = mid+1;
    int Arr[high-low+1] , k=0;
   for(int i = low ;i <= high ;i++)
{
          if(p > mid)      //checks if first part comes to an end or not .
                Arr[ k++ ] = A[ q++] ;
      else if ( q > high)   //checks if second part comes to an end or not
           Arr[ k++ ] = A[ p++ ];
    else if( A[ p ] < A[ q ])     //checks which part has smaller element.
                 Arr[ k++ ] = A[ p++ ];
else
                Arr[ k++ ] = A[ q++];
  }
  for (int p=0 ; p< k ;p ++)
{
    /* Now the real array has elements in sorted manner including both
        parts.*/
      A[ low++ ] = Arr[ p ] ;                         
  }
}

Code for Merge Sort in C:

#include <stdio.h>

void merge(int [], int, int, int);
void mergeSort(int [],int, int);
int main()
{
    int a[50],i,n;
    printf("How many number do you want to execute. ");
        scanf("%d", &n);
        printf("Enter the elements one by one. ");
       for(i = 0; i < n; i++)
    {
        scanf("%d", &a[i]);
    }
    mergeSort(a, 0, n - 1);
    printf("After merge sort:\n");
    for(i = 0;i < n; i++)
    {
          printf("%d   ",a[i]);
    }

   return 0;
}


void 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);
    }
}

void merge(int a[],int low,int mid,int high)
{
    int i, mi, k, lo, b[50];

    lo = low;
    i = low;
    mi = mid + 1;
    while ((lo <= mid) && (mi <= high))
    {
        if (a[lo] <= a[mi])
        {
            b[i] = a[lo];
            lo++;
        }
        else
        {
            b[i] = a[mi];
            mi++;
        }
        i++;
    }
    if (lo > mid)
    {
           for (k = mi; k <= high; k++)
        {
            b[i] = a[k];
            i++;
        }
    }
    else
    {
        for (k = lo; k <= mid; k++)
          {
              b[i] = a[k];
              i++;
          }
    }

    for (k = low; k <= high; k++)
    {
        a[k] = b[k];
    }
}


Example:

Output of the Program:

Time Complexity for Merge Sort:
  Worst Case : O(nlog n)
Best Case : O(nlog n)
Average Case: O(nlog n)