Java 歸併排序完整實現：從教科書算法到生產級優化與並行化

前言：歸併排序的工程價值

歸併排序是穩定、O(n log n) 最壤、外部排序基石、並行化友好的經典算法。雖然 JDK Arrays.sort(Object[]) 內部用 TimSort（歸併+插入混合），但手寫歸併排序是理解分治法、遞歸消除、輔助陣列複用、自底向上迭代、ForkJoin 並行的最佳載體。本文提供從教科書版到生產級並行版的完整演進。

1. 教科書遞歸版（原文改良）

public class MergeSortRecursive {

    public static void sort(int[] arr) {
        if (arr == null || arr.length < 2) return;
        int[] aux = new int[arr.length]; // 輔助陣列只分配一次
        sort(arr, aux, 0, arr.length - 1);
    }

    private static void sort(int[] arr, int[] aux, int lo, int hi) {
        if (lo >= hi) return; // 基線條件：單元素或空
        int mid = lo + (hi - lo) / 2; // 防溢出
        sort(arr, aux, lo, mid);
        sort(arr, aux, mid + 1, hi);
        merge(arr, aux, lo, mid, hi);
    }

    /** 合併兩個有序子陣列：arr[lo..mid] 和 arr[mid+1..hi] */
    private static void merge(int[] arr, int[] aux, int lo, int mid, int hi) {
        // 複製到輔助陣列
        System.arraycopy(arr, lo, aux, lo, hi - lo + 1);

        int i = lo, j = mid + 1;
        for (int k = lo; k <= hi; k++) {
            if (i > mid)                 arr[k] = aux[j++]; // 左半耗盡
            else if (j > hi)             arr[k] = aux[i++]; // 右半耗盡
            else if (aux[i] <= aux[j])   arr[k] = aux[i++]; // 穩定：<= 保證左優先
            else                         arr[k] = aux[j++];
        }
    }
}

關鍵優化點

1. 輔助陣列單次分配：避免每次遞歸 new int[]，減少 GC 壓力
2. System.arraycopy：JVM 內建優化，比手寫循環快 5-10 倍
3. 穩定性：aux[i] <= aux[j] 而非 <，保證相等元素左側優先
4. 邊界條件：lo >= hi 涵蓋單元素與空區間

2. 自底向上迭代版（消除遞歸、緩存友好）

public class MergeSortIterative {

    public static void sort(int[] arr) {
        if (arr == null || arr.length < 2) return;
        int n = arr.length;
        int[] aux = new int[n];

        // 子陣列大小：1, 2, 4, 8, ...
        for (int sz = 1; sz < n; sz <<= 1) {
            // 合併相鄰的兩個大小為 sz 的子陣列
            for (int lo = 0; lo < n - sz; lo += sz << 1) {
                int mid = lo + sz - 1;
                int hi = Math.min(lo + (sz << 1) - 1, n - 1);
                merge(arr, aux, lo, mid, hi);
            }
        }
    }

    // merge 方法同遞歸版
}

迭代版優勢

• 無遞歸棧溢出風險（極大數組）
• 內存訪問模式更規則，CPU 預取友好
• 易於並行化（外層循環可拆分任務）

3. 泛型版：支援任意 Comparable 類型

public class MergeSortGeneric {

    @SuppressWarnings("unchecked")
    public static > void sort(T[] arr) {
        if (arr == null || arr.length < 2) return;
        T[] aux = (T[]) new Comparable[arr.length]; // 類型擦除妥協
        sort(arr, aux, 0, arr.length - 1);
    }

    private static > void sort(T[] arr, T[] aux, int lo, int hi) {
        if (lo >= hi) return;
        int mid = lo + (hi - lo) / 2;
        sort(arr, aux, lo, mid);
        sort(arr, aux, mid + 1, hi);
        if (arr[mid].compareTo(arr[mid + 1]) <= 0) return; // 優化：已有序跳過合併
        merge(arr, aux, lo, mid, hi);
    }

    private static > void merge(T[] arr, T[] aux, int lo, int mid, int hi) {
        System.arraycopy(arr, lo, aux, lo, hi - lo + 1);
        int i = lo, j = mid + 1;
        for (int k = lo; k <= hi; k++) {
            if (i > mid)                 arr[k] = aux[j++];
            else if (j > hi)             arr[k] = aux[i++];
            else if (aux[i].compareTo(aux[j]) <= 0) arr[k] = aux[i++];
            else                         arr[k] = aux[j++];
        }
    }
}

關鍵優化：arr[mid] <= arr[mid+1] 跳過合併

若左右子陣列最大值 ≤ 右子陣列最小值，說明整體已有序，直接返回。近乎有序數據下接近 O(n)。

4. Comparator 版：外部比較策略

public static  void sort(T[] arr, Comparator cmp) {
    if (arr == null || arr.length < 2) return;
    T[] aux = (T[]) new Object[arr.length];
    sort(arr, aux, 0, arr.length - 1, cmp);
}

private static  void sort(T[] arr, T[] aux, int lo, int hi, Comparator cmp) {
    if (lo >= hi) return;
    int mid = lo + (hi - lo) / 2;
    sort(arr, aux, lo, mid, cmp);
    sort(arr, aux, mid + 1, hi, cmp);
    if (cmp.compare(arr[mid], arr[mid + 1]) <= 0) return;
    merge(arr, aux, lo, mid, hi, cmp);
}

private static  void merge(T[] arr, T[] aux, int lo, int mid, int hi, Comparator cmp) {
    System.arraycopy(arr, lo, aux, lo, hi - lo + 1);
    int i = lo, j = mid + 1;
    for (int k = lo; k <= hi; k++) {
        if (i > mid)                 arr[k] = aux[j++];
        else if (j > hi)             arr[k] = aux[i++];
        else if (cmp.compare(aux[i], aux[j]) <= 0) arr[k] = aux[i++];
        else                         arr[k] = aux[j++];
    }
}

5. 並行歸併排序：ForkJoinPool 實現

import java.util.concurrent.*;

public class ParallelMergeSort {

    private static final ForkJoinPool POOL = new ForkJoinPool(
        Runtime.getRuntime().availableProcessors()
    );

    public static void parallelSort(int[] arr) {
        if (arr == null || arr.length < 8192) { // 閾值同 JDK
            MergeSortRecursive.sort(arr);
            return;
        }
        int[] aux = new int[arr.length];
        POOL.invoke(new SortTask(arr, aux, 0, arr.length - 1));
    }

    private static class SortTask extends RecursiveAction {
        private final int[] arr, aux;
        private final int lo, hi;

        SortTask(int[] arr, int[] aux, int lo, int hi) {
            this.arr = arr; this.aux = aux; this.lo = lo; this.hi = hi;
        }

        @Override
        protected void compute() {
            if (hi - lo < 1024) { // 閾值切換串行
                MergeSortRecursive.sort(arr, aux, lo, hi);
                return;
            }
            int mid = lo + (hi - lo) / 2;
            SortTask left = new SortTask(arr, aux, lo, mid);
            SortTask right = new SortTask(arr, aux, mid + 1, hi);
            invokeAll(left, right); // 並行遞歸
            MergeSortRecursive.merge(arr, aux, lo, mid, hi); // 合併仍在當前線程
        }
    }
}

並行化關鍵決策

• 任務拆分閾值：hi - lo < 1024 切換串行，避免任務過細調度開銷
• 合併不並行：合併階段內存帶寬密集，多線程合併反而因緩存競爭變慢
• 共用輔助陣列：所有任務共享同一 aux，無額外分配

6. 外部排序擴展：大文件歸併（磁盤級）

當數據超出內存，需分片排序 + 多路歸併：

// 伪代碼流程
1. 分片讀入內存 (如 100MB/片)，內存排序寫入臨時文件
2. 使用 PriorityQueue (最小堆) 進行 k 路歸併
   - 每個臨時文件建一個 BufferedReader
   - 堆中保存 (當前值, 文件索引)
   - 反覆取堆頂寫入輸出文件，從對應文件讀下一值入堆
3. 清理臨時文件

Java 實現可參考 ExternalMergeSort 開源項目，核心是緩衝區管理、最小堆選擇、順序 I/O。

7. 效能基準 (JDK 21, 1000萬 int, 隨機數據)

8. 總結：何時手寫歸併排序？

生產環境決策：
├─ 基本類型排序 → 直接用 Arrays.sort / parallelSort (雙軸快排更快)
├─ 對象數組排序 → 直接用 Arrays.sort (TimSort 已高度優化、穩定)
├─ 教學/面試/算法題 → 手寫遞歸/迭代版，掌握分治、合併邏輯
├─ 特殊比較邏輯/不可修改源數組 → 手寫泛型/Comparator 版
├─ 超大數據並行排序 → ForkJoin 並行歸併 (或並行流 .parallel().sorted())
└─ 外部排序(磁盤數據) → 手寫多路歸併 + PriorityQueue

本文提供的代碼涵蓋：輔助陣列複用、System.arraycopy、已有序跳過、迭代消除遞歸、ForkJoin 並行、外部排序思路，可作為算法學習、面試準備、特殊場景落地的參考模板。