排序算法入门（三）：归并排序 —— 稳定、分治与外排序

import java.util.Arrays;

public class MergeSort {

    public static void sort(int[] a) {
        if (a == null || a.length < 2) {
            return;
        }
        // 整个排序过程共用这一块 O(n) 的临时空间。
        // 如果下沉到 merge 里 new，每层递归都会各申请一块长度接近区间的数组，
        // 总分配量从 O(n) 变成 O(n log n)，内存峰值和 GC 压力同时翻倍。
        int[] temp = new int[a.length];
        sort(a, temp, 0, a.length - 1);
    }

    private static void sort(int[] a, int[] temp, int lo, int hi) {
        if (lo >= hi) {
            return; // 长度 <= 1 的区间天然有序，这是递归的基线
        }
        int mid = lo + (hi - lo) / 2; // 不用 (lo + hi) / 2：(lo + hi) 会整数溢出成负数
        sort(a, temp, lo, mid);
        sort(a, temp, mid + 1, hi);
        merge(a, temp, lo, mid, hi);
    }

    private static void merge(int[] a, int[] temp, int lo, int mid, int hi) {
        // 左段最大值不大于右段最小值时整个区间已经有序，跳过这次搬运。
        // 真实数据里相邻两段已排好的情况很多，这一句省下的是实打实的 O(n) 拷贝。
        // （这个 <= 只是判断有序，与稳定性无关。）
        if (a[mid] <= a[mid + 1]) {
            return;
        }
        // 把待合并区间原样拷进 temp，然后从 temp 读、往 a 写。
        // 读写落在两块不重叠的内存上，结果能直接写回原数组，不用二次拷回。
        System.arraycopy(a, lo, temp, lo, hi - lo + 1);

        int i = lo;        // 左段读取游标
        int j = mid + 1;   // 右段读取游标
        int k = lo;        // 写回 a 的落点

        while (i <= mid && j <= hi) {
            // 相等时取左边。左段元素在原始数组里就排在右段之前，先取它，
            // 相对次序才保得住 —— 这就是稳定性的全部来源。
            // 改成 < 会先取右段元素，相等元素次序被翻转，排序不再稳定。
            if (temp[i] <= temp[j]) {
                a[k++] = temp[i++];
            } else {
                a[k++] = temp[j++];
            }
        }
        // 右段先耗尽时，把左段剩下的逐个搬过去。
        // 左段先耗尽时不需要任何动作：此时 k 恰好等于 j，
        // a[j..hi] 里放的就是右段剩余元素，位置已经正确。
        while (i <= mid) {
            a[k++] = temp[i++];
        }
    }

    public static void main(String[] args) {
        int[] a = {5, 2, 9, 2, 7, 1, 8, 3, 2};
        sort(a);
        System.out.println(Arrays.toString(a)); // [1, 2, 2, 2, 3, 5, 7, 8, 9]
    }
}

    /**
     * 独立的小方法：合并两个各自有序的数组，返回新数组。
     * 归并排序里的 merge 是它的“就地版”——复用原数组和一块临时区，
     * 内核完全一样：两个游标各扫一段，谁小先取谁。
     */
    public static int[] mergeTwoSorted(int[] left, int[] right) {
        int[] result = new int[left.length + right.length];
        int i = 0, j = 0, k = 0;

        while (i < left.length && j < right.length) {
            // 仍然是 <=：两边出现相同值时先取左边的，结果才稳定
            result[k++] = (left[i] <= right[j]) ? left[i++] : right[j++];
        }
        while (i < left.length) {
            result[k++] = left[i++]; // 右边先走完，左边剩余直接接上
        }
        while (j < right.length) {
            result[k++] = right[j++]; // 左边先走完，右边剩余直接接上
        }
        return result;
    }

    /**
     * 自底向上（迭代）版本，放在同一个类里。
     * 不递归，按段长 1、2、4、8…… 逐层合并相邻两段，直到段长覆盖整个数组。
     */
    public static void sortBottomUp(int[] a) {
        if (a == null || a.length < 2) {
            return;
        }
        int n = a.length;
        int[] temp = new int[n]; // 同样只在最外层分配一次，每一轮合并复用

        for (int len = 1; len < n; len <<= 1) {              // 段长每轮翻倍，共 log n 轮
            for (int lo = 0; lo < n - len; lo += len << 1) { // lo < n - len 保证右段至少有一个元素
                int mid = lo + len - 1;
                int hi = Math.min(lo + (len << 1) - 1, n - 1); // 右段不满 len 时必须夹住，否则越界
                merge(a, temp, lo, mid, hi);
            }
        }
    }