歸並排序算法詳解：分治思想、遞歸實現、迭代底層優化、Java 完整代碼與性能分析

核心思想：分治

1. 分解：將長度為 n 的數組遞歸二分，直到子數組長度為 1（天然有序）。
2. 解決：長度 1 直接返回。
3. 合併：將兩個有序子數組合併為一個有序數組（雙指針 O(n)）。

合併兩個有序數組（核心子過程）

// 將 a[left..mid] 和 a[mid+1..right] 合併到 tmp，再拷回 a
private static void merge(int[] a, int left, int mid, int right, int[] tmp) {
    int i = left, j = mid + 1, k = 0;
    while (i <= mid && j <= right) {
        tmp[k++] = (a[i] <= a[j]) ? a[i++] : a[j++]; // <= 保證穩定性
    }
    while (i <= mid) tmp[k++] = a[i++];
    while (j <= right) tmp[k++] = a[j++];
    System.arraycopy(tmp, 0, a, left, k); // 批量拷回，比循環快
}

遞歸版完整實現

public class MergeSortRecursive {
    public static void sort(int[] a) {
        if (a == null || a.length < 2) return;
        int[] tmp = new int[a.length]; // 外部分配，避免遞歸層層 new
        sort(a, 0, a.length - 1, tmp);
    }

    private static void sort(int[] a, int left, int right, int[] tmp) {
        if (left >= right) return;
        int mid = (left + right) >>> 1;
        sort(a, left, mid, tmp);
        sort(a, mid + 1, right, tmp);
        // 優化：若已有序（a[mid] <= a[mid+1]），跳過合併
        if (a[mid] > a[mid + 1]) merge(a, left, mid, right, tmp);
    }

    private static void merge(int[] a, int left, int mid, int right, int[] tmp) {
        // 見上文
    }
}

迭代版（自底向上，無遞歸棧溢出風險）

public class MergeSortIterative {
    public static void sort(int[] a) {
        if (a == null || a.length < 2) return;
        int n = a.length;
        int[] tmp = new int[n];

        for (int width = 1; width < n; width <<= 1) { // 子數組寬度 1,2,4,8...
            for (int left = 0; left < n; left += 2 * width) {
                int mid = Math.min(left + width - 1, n - 1);
                int right = Math.min(left + 2 * width - 1, n - 1);
                if (mid < right && a[mid] > a[mid + 1]) { // 需合併
                    merge(a, left, mid, right, tmp);
                }
            }
        }
    }
    // merge 同遞歸版
}

關鍵優化技巧

複雜度分析

• 時間：最好/平均/最壞均為 O(n log n)。分解高度 log n，每層合併總量 n。
• 空間：O(n) 輔助數組（非原地）。鏈表可 O(1) 空間。
• 穩定性：穩定（合併時 a[i] <= a[j] 先取左邊）。

與快速排序、堆排序對比

Java 實戰調用

int[] data = {5, 2, 9, 1, 5, 6};
MergeSortRecursive.sort(data); // 或 Iterative.sort(data)
System.out.println(Arrays.toString(data)); // [1, 2, 5, 5, 6, 9]

外部排序擴展（大文件排序）

1. 將大文件分塊讀入內存，單獨歸並排序後寫入臨時文件。
2. 對臨時文件進行 K 路歸並合併（優先隊列維護最小堆）。
3. 最終輸出有序大文件。

總結

歸並排序以「穩定、最壞 O(n log n)、易並行化」著稱。掌握「外部輔助數組、已有序跳過、小數組插入排序」三大優化，即可寫出生產級代碼。日常開發直接用 Arrays.sort()/Collections.sort()（JDK 8+ 為 TimSort，融合歸並與插入優化），僅在外部排序、鏈表排序、教學驗證時手寫。

1. 上一篇文章： Java 單例模式四大寫法深度對比：餓漢、靜態內部類、雙重檢查鎖、枚舉——含線程安全、序列化、反射攻擊防禦
2. 下一篇文章： Java static 與 final 關鍵字深度對比：修飾變量、方法、類、代碼塊的語義差異與最佳實踐

Java 程式設計入門

Java 進階教程：深入理解異常處理機制

程序開發過程中難免會遇到各種異常情況，無論是代碼邏輯錯誤、硬

Java 反編譯工具箱：7 款開源神器橫向評測

JVM 字節碼保留豐富元數據，使 Java 類文件極易反編譯

Java 與 MATLAB 繪製閉合多邊形完整對比：從算法原理到生產級視覺化

前言：多邊形繪製的幾何本質 「閉合多邊形」在計算機圖形學中定

JBuilder 9 + WebLogic 8.1 + Oracle 9i 安裝與配置指南

記錄 JBuilder 9、WebLogic Platfor