Sunday, December 22, 2013

Merge Sort in Java

public class MergeSort {

    public int A[], temp[]; //, size=0;

    MergeSort(int n) {
        A = new int[n];
        temp = new int[n];
        //size = n;
    }

    MergeSort() {
        A = null;
        temp = null;
        //size = 0;
    }

    public void mergeSort(int A[], int left, int right) {
        int mid;
        //System.out.println("A-len: " + this.A.length + " Temp-len: " + this.temp.length);
        if (left < right) {
            mid = (right + left) / 2;
            mergeSort(A, left, mid);
            mergeSort(A, mid + 1, right);
            merge(A, left, mid, right);
        }
    }

    public void merge(int A[], int left, int mid, int right) {
        int n1 = mid - left + 1;
        int n2 = right - mid;
        int L1[] = new int[n1];
        int L2[] = new int[n2];
     
        for (int i = 0; i < n1; i++) {
            L1[i] = A[left + i];
        }

        for (int i = 0; i < n2; i++) {
            L2[i] = A[mid + i + 1];
        }

        int i = 0, j = 0, k = left;
        while (i < n1 && j < n2) {
            if (L1[i] <= L2[j]) {
                A[k] = L1[i];
                i++;
            } else {
                A[k] = L2[j];
                j++;
            }
            k++;
        }

        while (i < n1) {
            A[k] = L1[i];
            i++;
            k++;
        }

        while (j < n2) {
            A[k] = L2[j];
            j++;
            k++;
        }

    }

    public void printArr() {
        System.out.print("Sorted: ");
        for (int i = 0; i < this.A.length; i++) {
            System.out.print(this.A[i] + ", ");
        }
        System.out.println();
    }

    public static void main(String args[]) {
        MergeSort sort = new MergeSort();
        sort.A = new int[]{2, 4, 5, 7, 1, 2, 3, 6};
        sort.temp = new int[8];
        sort.mergeSort(sort.A, 0, 7);
        // print sorted Array
        sort.printArr();
    }
}

No comments:

Post a Comment