MergeSort.java

/**
 * Created by lan2720 on 15/11/10.
 */
public class MergeSort {
    public static void merge_1(int[] A, int p, int q, int r){
        /**
         * 这种merge使用了哨兵
         */
        // get the number of integer of each subArray
        int n1 = q - p + 1;
        int n2 = r - q;

        int[] L = new int[n1+2]; // 1~n1, L[n1+1]=inf
        int[] R = new int[n2+2];

        // copy the original subArray from A to L and R
        int i,j;
        for(i = 1; i <= n1; i++) L[i] = A[p + i - 1];
        for(j = 1; j <= n2; j++) R[j] = A[q + j];
        L[n1+1] = Integer.MAX_VALUE;
        R[n2+1] = Integer.MAX_VALUE;

        i = 1;
        j = 1;
        for(int k = p; k <= r; k++) {
            if(L[i] <= R[j]) A[k] = L[i++];
            else A[k] = R[j++];
        }
    }

    public static void merge_2(int[] A, int p, int q, int r){
        /**
         * 这种merge不用哨兵，且当任意一堆所有元素均被复制回A就立即停止，将另一个数组的剩余元素复制回A
         */
        // 对于merge为什么要有一个中间index？因为从哪里split的，有一个idx(q)，就从哪里merge起来
        int n1 = q - p + 1;
        int n2 = r - q;

        int[] L = new int[n1+1]; // 1~n1
        int[] R = new int[n2+1];

        int i, j;
        for(i = 1; i <= n1; i++) L[i] = A[p+i-1];
        for(j = 1; j <= n2; j++) R[j] = A[q+j];

        i = 1;
        j = 1;
        for(int k = p; k <= r; k++) {
            if(i > n1) A[k] = R[j++];
            else if(j > n2) A[k] = L[i++];
            else if(L[i] <= R[j]) A[k] = L[i++];
            else A[k] = R[j++];
        }
    }

    public static void mergeSort(int[] A, int p, int r){
        // 如果p == r 说明子数组只有一个元素了，此时已经有序，进行返回merge
        if (p < r) {
            int q = (p+r)/2;
            mergeSort(A, p, q);
            mergeSort(A, q+1, r);
            merge_2(A, p, q, r);
        }
    }


    public static void main(String args[]){
        int[] a = {6,2,9,1,8,7};
        // 这里的a是这个数组对象的一个引用，在merge函数中直接对这个对象的内存进行了修改
        mergeSort(a, 0, 5);
        // 因此a再次访问其每一个元素时，元素就已经是排序之后的顺序了
        for(int m = 0; m < a.length; m++)
            System.out.println(a[m]);
    }
}