Wednesday, June 22, 2011

How to implement Merge Sort Using Java

By running the below program u can clearly understand how the merge sort works...
this program is to sort ten integers.


 // This program is to demonstrate how to implement mergesort in java..  
 // W.M.S Fernando.  
 //18/06/2011....  
 import java.util.Scanner;  
 public class MergeSort {  
    private final int num=10;  
     private int [] A=new int[num];  
   public static void main(String[] args) {  
     // TODO Auto-generated method stub  
   MergeSort m=new MergeSort();    
     m.Merge_S(m.getNum(), 0, 9);  
     m.show();  
   }  
 public MergeSort(){  
   Scanner input=new Scanner(System.in);  
   System.out.println("Enter the numbers to sort:");  
   for(int i=0;i<A.length;i++){  
     A[i]=input.nextInt();  
   }  
 }    
 public void Merge_S(int [] W,int p,int r){  
   int q=0;  
   System.out.println("P: "+p+" Q: "+q+" R: "+r+" out from if condition.... ");  
   if(p<r){  
     q=(p+r)/2;  
     System.out.println("P: "+p+" Q: "+q+" R: "+r+" In the if condition....");  
     System.out.println("Merge 1");  
     System.out.println("P: "+p+" Q: "+q+" R: "+r+" Befor merge_S 1");  
     ///////////////////////////  
     Merge_S(A,p,q);  
     ///////////////////////  
     System.out.println("P: "+p+" Q: "+q+" R: "+r+" After Merge_S 1");  
     System.out.println("Merge 2");  
     System.out.println("P: "+p+" Q: "+q+" R: "+r+" Befor Merge_S 2");  
     /////////////////////////  
     Merge_S(A,q+1,r);  
     /////////////////////////  
     System.out.println("P: "+p+" Q: "+q+" R: "+r+" After Merge_S 2");  
     System.out.println("P: "+p+" Q: "+q+" R: "+r+" Before the merge function..");  
     //////////////////////////////////////  
     MergeSort.Merge(A,p,q,r,100);  
     /////////////////////////////////////  
     System.out.println("P: "+p+" Q: "+q+" R: "+r+" After Merge");  
   }  
 }  
 public static void Merge(int [] W,int p,int q,int r,int Max){  
   System.out.println("Merge function executes.......");  
   int nL=q-p+1;  
   int nR=r-q;  
   System.out.println("nL: "+nL+" nR: "+nR);  
   int [] L=new int[nL+1];  
   int [] R=new int[nR+1];  
   L[nL]=Max+1;  
   R[nR]=Max+1;  
   for(int i=0;i<L.length-1;i++){  
     L[i]=W[p+i];  
     System.out.println("L["+i+"]: "+L[i]);  
   }  
   for(int j=0;j<R.length-1;j++){  
     R[j]=W[q+1+j];  
    System.out.println("R["+j+"]: "+R[j]);  
   }  
 int i=0;  
 int j=0;  
   for(int k=p;k<=r;k++){  
     if(L[i]<=R[j]){  
       W[k]=L[i];  
       System.out.println("W["+k+"]: "+W[k]);  
       i++;  
     }  
     else{  
       W[k]=R[j];  
       j ++;  
     System.out.println("W["+k+"]: "+W[k]);  
     }  
   }  
 }    
 public int Max(int [] W){  
   int max=0;  
   for(int i=0;i<W.length;i++){  
     if(W[i]>=W[i+1]){  
       max=W[i];  
     }  
     else{  
       max=W[i+1];  
     }  
   }  
   return max;  
 }  
 public int [] getNum(){  
   return A;  
 }  
 public void show(){  
   System.out.println("Here is the sorted Array....");  
   for(int i=0;i<A.length;i++){  
     System.out.print(" "+A[i]);  
   }  
 }  
 }