Merge Sort

Merge Sort algorithm and Program in C

We have seen sorting using bubble sort, Insertion sort method which are not much efficient methods. Now we shall use a divide and conquer strategy to improve the performance of our sorting algorithm. Merge sort is a recursive algorithm which splits a list to be sorted in half. If the list is empty or has one item, the list is already sorted which is used as base case here. If the list has more than one item we split the list in half and recursively invoke merge sort on both the halves. Once the two halves are sorted, a merge procedure is called, which takes two lists and merge them into a single sorted list.

Splitting list into smaller lists

Merging the list to form a single sorted list

This algorithm has the complexity O(NlogN). The merge sort program in C is as shown below.

Code:

#include<stdio.h>
void merge(int A[],int p,int q,int r){
     int i,j,k,n1,n2;
     n1=q-p+1;
     n2=r-q;
     int L[n1+1],R[n2+1];//taking two arrays for left and right part of the mid point
     for(i=0;i<n1;i++)
          L[i]=A[p+i];
     for(i=0;i<n2;i++)
          R[i]=A[q+1+i];
     L[n1]=2147483647;
     R[n2]=2147483647;//assuming all the values in the will be less than the max value
     i=0;j=0;
     for(k=p;k<=r;k++){// important to take k<=r here because we are using r as 1 less than total number of elements in array
          if(L[i]<=R[j]){
               A[k]=L[i];
               i++;
          }
          else{
               A[k]=R[j];
               j++;
          }
     }
}

void merge_sort(int A[],int p,int r){
     int q;
     if(p<r){
          //q is the mid point
          //q=(p+r)/2; // it can overflow so do not use this to find the mid point
          q=p+(r-p)/2; // this will never ovweflow
          merge_sort(A,p,q);
          merge_sort(A,q+1,r);
          merge(A,p,q,r);
     }
}

void print(int A[],int p,int r){
     int i;
     for(i=p;i<=r;i++)
          printf("%d ",A[i]);
}

int main(){
    int A[]={54,26,93,17,77,31,44,55,20},i,p,r; //p is the first index of array // r is the last index of the array
    p=0;
    r=(sizeof(A)/sizeof(A[0]))-1;
    printf("List before sorting: ");
    print(A,p,r);
    merge_sort(A,p,r);
    printf("\n\nList after sorting: ");
    print(A,p,r);
    return 0;
}