Merge Sort

Merge Sort follows the rule of Divide and Conquer. But it doesn't divides the list into two halves. In merge sort the unsorted list is divided into N sublists, each having one element, because a list of one element is considered sorted. Then, it repeatedly merge these sublists, to produce new sorted sublists, and at lasts one sorted list is produced.

Merge Sort is quite fast, and has a time complexity of O(n log n). It is also a stable sort, which means the "equal" elements are ordered in the same order in the sorted list.

Algorithm

Merge sort keeps on dividing the list into equal halves until it can no more be divided. By definition, if it is only one element in the list, it is sorted. Then, merge sort combines the smaller sorted lists keeping the new list sorted too.

• Step 1 - if it is only one element in the list it is already sorted, return.

• Step 2 - divide the list recursively into two halves until it can no more be divided.

• Step 3 - merge the smaller lists into new list in sorted order.

Example:

Listing: Following program is showing the implementation of Merge Sort.

/* 
* C Program to Input Few Numbers & Perform Merge Sort on them using Recursion 
*/ 

#include <stdio.h> 

void mergeSort(int [], int, int, int); 
void partition(int [],int, int); 

int main() 
{ 
    int list[50]; 
    int i, size; 

    printf("Enter total number of elements:"); 
    scanf("%d", &size); 
    printf("Enter the elements:\n"); 
    for(i = 0; i < size; i++) 
    { 
         scanf("%d", &list[i]); 
    } 
    partition(list, 0, size - 1); 
    printf("After merge sort:\n"); 
    for(i = 0;i < size; i++) 
    { 
         printf("%d   ",list[i]); 
    } 

   return 0; 
} 

void partition(int list[],int low,int high) 
{ 
    int mid; 

    if(low < high) 
    { 
        mid = (low + high) / 2; 
        partition(list, low, mid); 
        partition(list, mid + 1, high); 
        mergeSort(list, low, mid, high); 
    } 
} 

void mergeSort(int list[],int low,int mid,int high) 
{ 
    int i, mi, k, lo, temp[50]; 

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

    for (k = low; k <= high; k++) 
    { 
        list[k] = temp[k]; 
    } 
} 

Output: 

    Enter total number of elements:5 
    Enter the elements: 
    12 
    36 
    22 
    76 
    54 
    After merge sort: 
    12   22   36   54   76