Java 合併排序演算法完整教學：遞歸與迭代雙重實作

前言

合併排序是經典的「分治法」代表，以穩定的 O(n log n) 時間複雜度著稱，且為穩定排序。本文將從核心思想、遞歸實作、自底向上迭代實作、複雜度分析到實戰優化，完整呈現這項必會演算法。

核心思想：分治三部曲

1. 分解：將陣列對半切分，直到子陣列長度為 1（視為有序）。
2. 解決：遞歸排序左右子陣列。
3. 合併：將兩個有序子陣列合併為一個有序陣列。

合併關鍵：雙指針線性掃描，時間 O(n)、額外空間 O(n)。

遞歸版實作（自頂向下）

public class MergeSortRecursive {
    public void sort(int[] a) {
        int[] aux = new int[a.length];
        mergeSort(a, 0, a.length - 1, aux);
    }

    private void mergeSort(int[] a, int lo, int hi, int[] aux) {
        if (hi <= lo) return;
        int mid = lo + (hi - lo) / 2;
        mergeSort(a, lo, mid, aux);
        mergeSort(a, mid + 1, hi, aux);
        merge(a, lo, mid, hi, aux);
    }

    private void merge(int[] a, int lo, int mid, int hi, int[] aux) {
        // 複製到輔助陣列
        for (int k = lo; k <= hi; k++) aux[k] = a[k];

        int i = lo, j = mid + 1;
        for (int k = lo; k <= hi; k++) {
            if (i > mid)              a[k] = aux[j++];
            else if (j > hi)          a[k] = aux[i++];
            else if (aux[i] <= aux[j]) a[k] = aux[i++];
            else                       a[k] = aux[j++];
        }
    }
}

關鍵點：使用單一輔助陣列 aux 避免重複分配記憶體；<= 保證穩定性。

迭代版實作（自底向上）

public class MergeSortIterative {
    public void sort(int[] a) {
        int N = a.length;
        int[] aux = new int[N];
        for (int sz = 1; sz < N; sz += sz) {          // 子陣列大小：1, 2, 4, 8...
            for (int lo = 0; lo < N - sz; lo += sz + sz) {
                int mid  = lo + sz - 1;
                int hi   = Math.min(lo + sz + sz - 1, N - 1);
                merge(a, lo, mid, hi, aux);
            }
        }
    }
    // merge 方法同上
}

優勢：無遞歸呼叫棧開銷，適合嵌入式環境；邏輯較簡潔。

複雜度分析

實戰優化技巧

• 小陣列切換插入排序：當 hi - lo <= 7 時改用插入排序，減少遞歸開銷。
• 檢查是否已有序：合併前若 a[mid] <= a[mid+1] 則跳過合併。
• 避免複製回原陣列：雙陣列輪換角色（a、aux 交換引用），省去複製步驟。
• 原地合併：進階技巧，空間降至 O(1) 但實作複雜，通常不值得。

應用場景

• 外部排序（大檔案排序、資料庫合併）
• 需要穩定排序的業務（訂單按金額再按時間）
• 並行運算基礎（MapReduce、ForkJoinPool）

總結

合併排序以穩定、確定的 O(n log n) 表現，成為教學與工程的標桿演算法。掌握遞歸與迭代雙重實作，並理解優化細節，能在面試與實戰中遊刃有餘。