Wednesday, April 10, 2013

Merge Sort Recursive


public class Merge {
    public int [] data;
    private int [] helper;
   
   
    public Merge(int[] a){
        data=a;
        this.helper = new int[a.length];
    }
   
    public void splitAndMerge(int begin, int end){
       
        if(begin<end){
            int middle = (begin+end)/2;
            splitAndMerge(begin, middle);
            splitAndMerge(middle+1, end);
            MergeSort(begin, middle, end);
        }
    }
   
    public void MergeSort(int begin, int middle, int end){
         for(int i=begin;i<=end;i++){
             helper[i]=data[i];
         }
   
         int x=begin;
         int y=middle+1;
         int z=begin;
       
         while(x<=middle&&y<=end){
             if(helper[x]<=helper[y]){
                    data[z]=helper[x];
                    x++;
                    z++;
             }
             else{
                     data[z]=helper[y];
                     y++;
                     z++;
             }
         }
       
         //Copy the rest of left to the array
         while(x<=middle){
             data[z]=helper[x];
             z++;
             x++;
         }
    }
}

No comments :

Post a Comment