Java 實現歸併排序：分治法遞歸與迭代完整代碼解析

演算法核心思想

歸併排序是典型的分治法：

1. 分解：將陣列二分為左右兩半，遞歸排序。
2. 解決：單元素陣列天然有序。
3. 合併：將兩個有序子陣列合併為一個有序陣列（雙指針 O(N)）。

時間複雜度：O(N log N)（最好/最壞/平均），空間複雜度 O(N)（輔助陣列），穩定排序。

遞歸版完整代碼

import java.util.Arrays;

public class MergeSort {
    public static void main(String[] args) {
        int[] a = {6, -2, 7, 8, 3, 4, 12, 1, 0, -3, -8, 3, 4, 7};
        System.out.println("排序前：" + Arrays.toString(a));
        sort(a, 0, a.length - 1);
        System.out.println("排序後：" + Arrays.toString(a));
    }

    public static void sort(int[] a, int low, int high) {
        if (low < high) {
            int mid = (low + high) >>> 1; // 防溢出
            sort(a, low, mid);
            sort(a, mid + 1, high);
            merge(a, low, mid, high);
        }
    }

    private static void merge(int[] a, int low, int mid, int high) {
        int[] temp = new int[high - low + 1];
        int i = low, j = mid + 1, k = 0;

        // 合併兩有序區間
        while (i <= mid && j <= high) {
            temp[k++] = (a[i] <= a[j]) ? a[i++] : a[j++]; // <= 保證穩定性
        }
        while (i <= mid) temp[k++] = a[i++];
        while (j <= high) temp[k++] = a[j++];

        // 複製回原陣列
        System.arraycopy(temp, 0, a, low, temp.length);
    }
}

迭代版（自底向上）

public static void sortIterative(int[] a) {
    int n = a.length;
    int[] temp = new int[n];
    for (int width = 1; width < n; width <<= 1) { // 子陣列寬度 1,2,4,8...
        for (int i = 0; i < n; i += 2 * width) {
            int low = i;
            int mid = Math.min(i + width - 1, n - 1);
            int high = Math.min(i + 2 * width - 1, n - 1);
            merge(a, temp, low, mid, high);
        }
        // 交換 a 與 temp 角色，避免重複複製
        int[] swap = a; a = temp; temp = swap;
    }
    // 若最終結果在 temp，複製回 a
    if (a != temp) System.arraycopy(a, 0, temp, 0, n);
}

private static void merge(int[] src, int[] dest, int low, int mid, int high) {
    int i = low, j = mid + 1, k = low;
    while (i <= mid && j <= high) dest[k++] = (src[i] <= src[j]) ? src[i++] : src[j++];
    while (i <= mid) dest[k++] = src[i++];
    while (j <= high) dest[k++] = src[j++];
}

關鍵優化點

• 臨界值切換插入排序：子陣列長度 ≤ 16 時改用插入排序，減少遞歸開銷。
• 檢查是否已有序：合併前若 a[mid] <= a[mid+1]，直接返回，跳過合併。
• 雙緩衝區交換：迭代版交換 src/dest 引用，省去 System.arraycopy 開銷。
• 平行化：ForkJoinPool 併行處理左右半部，Java 8+ Arrays.parallelSort 內部即採用平行歸併。

與快速排序對比