Java 歸併排序實作教學：分治法遞迴與迭代雙版本

演算法原理

歸併排序採用 分治法：

1. 分解：將陣列對半分割，直到單一元素（天然有序）。
2. 解決：遞迴排序左右子陣列。
3. 合併：將兩個有序子陣列合併為一個有序陣列。

時間複雜度 O(n log n)，空間複雜度 O(n)，穩定排序。

遞迴版本（教學標準寫法）

public class MergeSortRecursive {
    private int[] aux; // 輔助陣列，避免重複分配

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

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

    private void merge(int[] a, int lo, int mid, int hi) {
        // 複製到輔助陣列
        System.arraycopy(a, lo, aux, lo, hi - lo + 1);

        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++];
        }
    }

    public static void main(String[] args) {
        int[] data = {38, 27, 43, 3, 9, 82, 10};
        new MergeSortRecursive().sort(data);
        System.out.println(Arrays.toString(data)); // [3, 9, 10, 27, 38, 43, 82]
    }
}

迭代版本（自底向上，無遞迴呼叫）

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

    private void merge(int[] a, int[] aux, int lo, int mid, int hi) {
        System.arraycopy(a, lo, aux, lo, hi - lo + 1);
        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++];
        }
    }
}

效能優化技巧

• 小陣列改用插入排序：sz <= 7 時切換，減少遞迴開銷。
• 檢查是否已有序：合併前若 a[mid] <= a[mid+1] 直接跳過。
• 避免重複複製：雙緩衝交換 a、aux 角色，省去 System.arraycopy。

與 Arrays.sort() 比較

實務建議：生產碼直接用 Arrays.sort() 或 Collections.sort()；教學、面試、特殊穩定性需求時手寫 MergeSort。