Algorithm, Source Code/Program For Merge Sort in C and JAVA

Add This To Del.icio.us Share on Facebook StumbleUpon This Add to Technorati Digg This

Merge Sort is the Best Example Of Divide and Conquer Algorithm In this Algorithm First Of all the List is divided into Sub Division and this Process will be go on until You'll get Smallest Unit Of that List. The Operation Performing Previously is Divide Operation Now We will Go On For the Conquer Operation i.e. Sorting all the individual List and Place them in a List.

Well This seems to be some Confusing one But Don't Worry we Will Give you Full Tutorial in this Article.

Algorithm Of Merge Sort

There are Two Sub-Routine Used in this Whole Sorting process One is For Divide and Other One is For Conquer Process

MERGE-SORT(A,p,r)
    1. if p < r
    2.     q = [( p + r )/2]
    3.     MERGE-SORT(A,p,q)
    4.     MERGE-SORT(A,q+1,r)
    5.     MERGE(A,p,q,r)
    6.    END

MERGE(A,p,q,r)
   1. n1= q-p+1
   2. n2=r-q
   3. let L[1....n1+1] and R[1.....n2+1] be the new Array
   4. for i=1 to n1
   5.         L[i] = A[p+i-1]
   6. for j=1 to n2
   7.        R[j] = A[q+j]
   8. L[n1+1] = 0
   9. R[n2 + 1] =0
  10. i=1
  11. j=1
  12. for k= p to r
  13.    if L[i] <= R[j]
  14.     A[k] = L[i]
  15.     i = i+1
  16.   else A[k] = R[j]
  17.     j= j +1
  18. end

C Program For Merge Sort

void partition(int arr[],int low,int high){

    int mid;

    if(low<high){

         mid=(low+high)/2;

         partition(arr,low,mid);

         partition(arr,mid+1,high);

         mergeSort(arr,low,mid,high);

    }

}

void mergeSort(int arr[],int low,int mid,int high){

    int i,m,k,l,temp[MAX];

    l=low;

    i=low;

    m=mid+1;

    while((l<=mid)&&(m<=high)){

         if(arr[l]<=arr[m]){

             temp[i]=arr[l];

             l++;

         }

         else{

             temp[i]=arr[m];

             m++;

         }

         i++;

    }

    if(l>mid){

         for(k=m;k<=high;k++){

             temp[i]=arr[k];

             i++;

         }

    }

    else{

         for(k=l;k<=mid;k++){

             temp[i]=arr[k];

             i++;

         }

    }

   

    for(k=low;k<=high;k++){

         arr[k]=temp[k];

    }

}

Java Source Code For Merge Sort Program

package com.codingfunda.sorting;

public class MyMergeSort {
 
 private int[] array;
 private int[] tempMergArr;
 private int length;

 public static void main(String a[]){
  
  int[] inputArr = {45,23,11,89,77,98,4,28,65,43};
  MyMergeSort mms = new MyMergeSort();
  mms.sort(inputArr);
  for(int i:inputArr){
      System.out.print(i);
      System.out.print(" ");
     }
 }
 
 public void sort(int inputArr[]) {
  this.array = inputArr;
  this.length = inputArr.length;
  this.tempMergArr = new int[length];
  doMergeSort(0, length - 1);
 }

 private void doMergeSort(int lowerIndex, int higherIndex) {
  
  if (lowerIndex < higherIndex) {
   int middle = lowerIndex + (higherIndex - lowerIndex) / 2;
   // Below step sorts the left side of the array
   doMergeSort(lowerIndex, middle);
   // Below step sorts the right side of the array
   doMergeSort(middle + 1, higherIndex);
   // Now merge both sides
   mergeParts(lowerIndex, middle, higherIndex);
  }
 }

 private void mergeParts(int lowerIndex, int middle, int higherIndex) {

  for (int i = lowerIndex; i <= higherIndex; i++) {
   tempMergArr[i] = array[i];
  }
  int i = lowerIndex;
  int j = middle + 1;
  int k = lowerIndex;
  while (i <= middle && j <= higherIndex) {
   if (tempMergArr[i] <= tempMergArr[j]) {
    array[k] = tempMergArr[i];
    i++;
   } else {
    array[k] = tempMergArr[j];
    j++;
   }
   k++;
  }
  while (i <= middle) {
   array[k] = tempMergArr[i];
   k++;
   i++;
  }

 }
}

For Further Reading,

ALGO, C, JAVA