Like Us On Facebook

Follow Us On Twitter

Drop Down Menu

Tuesday 8 January 2013

Merge Sort Algorithm And C Code

Merge sort is a sorting technique, which is  based on comparison sorting algorithm, having complexity O(n log n). It is one of the types of stable sort, meaning, that in its implementation, input order of equal elements is preserved in the sorted output.  It was invented by John von Neumann in 1945. Merge sort is a divide and conquer algorithm.

The concept of Merge Sort is based on the following principle:

Divide the unsorted list into 'n' sub-lists, each containing 1 element (a list of 1 element is considered sorted).
Repeatedly merge sub-lists to produce new sub-lists until there is only 1 sub-list remaining. This will be the sorted list.

Algorithm for Merge Sort:

/* Double-Click To Select Code */

function merge_sort(list m)
    // if list size is 0 (empty) or 1, consider it sorted and return it
    // (using less than or equal prevents infinite recursion for a zero length m)
    if length(m) <= 1
        return m
    // else list size is > 1, so split the list into two sublists
    var list left, right
    var integer middle = length(m) / 2
    for each x in m before middle
         add x to left
    for each x in m after or equal middle
         add x to right
    // recursively call merge_sort() to further split each sublist
    // until sublist size is 1
    left = merge_sort(left)
    right = merge_sort(right)
    // merge the sublists returned from prior calls to merge_sort()
    // and return the resulting merged sublist
    return merge(left, right)
In this example, the merge function merges the Left and Right sublists.

/* Double-Click To Select Code */

function merge(left, right)
    var list result
    while length(left) > 0 or length(right) > 0
        if length(left) > 0 and length(right) > 0
            if first(left) <= first(right)
                append first(left) to result
                left = rest(left)
            else
                append first(right) to result
                right = rest(right)
        else if length(left) > 0
            append first(left) to result
            left = rest(left)
        else if length(right) > 0
            append first(right) to result
            right = rest(right)
    end while
    return result


Here is the C Code for Merge Sort:


/* Double-Click To Select Code */

#include <stdio.h>
#include<conio.h>
 
void mergesort(int arr[], int l, int h);
 
void main(void) 
{
 int array[100],n,i = 0; 
 clrscr();
 printf("Enter the number of elements to be sorted: ");
 scanf("%d",&n);
 printf("\nEnter the elements to be sorted: \n");
 for(i = 0 ; i < n ; i++ )
 {
  printf("\tArray[%d] = ",i);
  scanf("%d",&array[i]);
 }
 
 
 printf("\nBefore Mergesort:");  //Array Before Mergesort
 for(i = 0; i < n; i++)
 {
  printf("%4d", array[i]);
 }
 printf("\n");
 
 mergesort(array, 0, n - 1); 

 printf("\nAfter Mergesort:");  //Array After Mergesort
 for(i = 0; i < n; i++)
 {
  printf("%4d", array[i]);
 }
 printf("\n");
 getch();
}
 
void mergesort(int arr[], int l, int h) 
{
 int i = 0;
 int length = h - l + 1;
 int pivot  = 0;
 int merge1 = 0;
 int merge2 = 0;
 int temp[100];
 
 if(l == h)
 return;
 
 pivot  = (l + h) / 2;
 
 mergesort(arr, l, pivot);
 mergesort(arr, pivot + 1, h);
  
 for(i = 0; i < length; i++)
 {
  temp[i] = arr[l + i];
 }
 
 merge1 = 0;
 merge2 = pivot - l + 1;
 
 for(i = 0; i < length; i++) 
 {
  if(merge2 <= h - l)
  {
   if(merge1 <= pivot - l)
   {
    if(temp[merge1] > temp[merge2])
    {
     arr[i + l] = temp[merge2++];
    }

    else
    {
     arr[i + l] = temp[merge1++];
    }
   }

   else
   {
    arr[i + l] = temp[merge2++];
   }
  }

  else
  {
   arr[i + l] = temp[merge1++];
  }
 }
}

Output of Program:



Merge Sort Algorithm And C Code

Please Comment If You Liked This Post !! 

This article uses material from the Wikipedia article Merge Sort which is released under the Creative Commons Attribution-Share-Alike License 3.0


Do you like this post? Please link back to this article by copying one of the codes below.

URL: HTML link code: Forum link code: