归并排序模板（Java）

《算法导论》学习记录

    /**
     * 归并排序
     * O(nlogn)
     * @param A 待排序的数组
     * @param p 数组的左端点：1
     * @param r 数组的右端点：A.length
     */
    public static void MERGESORT(int[] A, int p, int r) {
        if(p < r) {
            int q = (p + r) / 2;
            // 1. 先分解待排序的数组，成两个子序列
            MERGESORT(A, p, q);
            MERGESORT(A, q + 1, r);
            // 2.3. 解决排序并合并
            MERGE_UP(A, p, q, r);
        }
    }

    public static void MERGE_UP(int[] A, int p, int q, int r) {
        // 分别取两个子序列的长度新建两个数组（此时两个子序列已经各自排好序）
        int lenleft = q - p + 1;
        int lenright = r - q;
        // 在数组的末尾设立一个极值（设置哨兵）
        int[] L = new int[lenleft + 1];
        int[] R = new int[lenright + 1];

        for(int i = 0; i < lenleft; i++) {
            L[i] = A[p - 1 + i];
        }
        for(int j = 0; j < lenright; j++) {
            R[j] = A[q + j];
        }
        L[lenleft] = Integer.MAX_VALUE;  // 取极值
        R[lenright] = Integer.MAX_VALUE;

        // 合并两个子序列（归并排序）
        int i = 0, j = 0;
        for(int k = p - 1; k < r; k++) { // 由于 Java 数组从 0 下标开始，所以要做一些处理
            // 把 <= 换成 >= 即可变成降序归并，同时需要把 MAX_VALUE 改成 MIN_VALUE
            if(L[i] <= R[j]) {
                A[k] = L[i++];
            }
            else {
                A[k] = R[j++];
            }
        }
        // 此时 A[p..r] 已排好序
    }