Tuesday, 3 April 2012

MergeSort with primitive array

Running time - O(n log n)

Java Implementation with primitive array

public class MergeSort {

    /**
     * @param args
     */
    public static void main(String[] args) {
        int[] input = new int[]{8,7,6,5,4,3,2,1,10};
        System.out.println(" INPUT :: "+ input);
        int[] output = splitMerge(input,0,input.length);
        for(int x=0;x < output.length;x++){
            System.out.print(" OUTPUT :: "+ output[x] + " ");
        }

    }
   
    public static int[] splitMerge(int[] data, int start, int length){
        if(length > 1) {
            int l = length/2;
            int l1 = length - l;
            splitMerge(data, start, l);
            splitMerge(data, start + l, l1);
            merge(data, start, l, l1);
        }
        return data;
    }
   
    private static void merge(int[] data, int start, int l, int l1 ){
        int[] temp = new int[l+l1];;
        int i = 0;
        int j = 0 ;
        int k = 0;
        while(i < l && j < l1){
            if(data[start + i] <= data[start + l + j]){
                temp[k] = data[start + i];
                i++;
            }
            else if(data[start + l + j] < data[start + i]){
                temp[k] = data[start + l + j];
                j++;
            }
            k++;
        }
        while(j < l1){
            temp[k] = data[start + l + j];
            j++;
            k++;
        }
        while(i < l){
            temp[k] = data[start + i];
            i++;
            k++;
        }
        for(int m=0;m < temp.length;m++){
            data[start + m] = temp[m];
        }
        System.out.println();
    }

}

No comments:

Post a Comment