Java 排序算法總結：歸併排序原理、實現與優化策略

歸併排序核心思想

歸併排序採用分治法：

1. 分解：遞歸將數組二分，直到單元素（天然有序）。
2. 解決：單元素無需操作。
3. 合併：將兩個有序子數組合併為一個有序數組（雙指針線性合併）。

算法特性

• 時間複雜度：最好/最壞/平均均為 O(n log n)，極其穩定。
• 空間複雜度：數組實現需 O(n) 輔助空間；鏈表可 O(1) 空間（指針重組）。
• 穩定性：穩定，合併時優先取左側元素，保持相等元素相對順序。
• 非自適應：數據分佈不影響性能。

Java 經典實現（自頂向下遞歸）

public class MergeSort {
    private static int[] aux; // 輔助數組，避免重複分配

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

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

    // 合併 [lo..mid] 和 [mid+1..hi]
    private static void merge(int[] arr, 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[j] < aux[i]) arr[k] = aux[j++]; // < 保證穩定性
            else                      arr[k] = aux[i++];
        }
    }
}

自底向上迭代版（無遞歸，更適合大數組）

public static void sortBU(int[] arr) {
    int n = arr.length;
    int[] aux = new int[n];
    for (int sz = 1; sz < n; sz <<= 1) { // 子數組大小：1,2,4,8...
        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);
        }
    }
}

// 合併輔助方法（複用 aux）
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[j] < aux[i]) arr[k] = aux[j++];
        else                      arr[k] = aux[i++];
    }
}

關鍵優化策略

• 小數組切換插入排序：子數組長度 ≤ 7 時用插入排序，減少遞歸開銷（Java Arrays.sort 對象數組即採用此策略）。
• 檢查是否已有序：合併前若 arr[mid] <= arr[mid+1] 則跳過合併。
• 避免重複複製：在遞歸層級間交換 arr 與 aux 角色，省去複製回原數組步驟。
• 並行歸併：Java 8+ Arrays.parallelSort() 利用 ForkJoinPool 並行排序子數組再合併。

應用場景

• 外部排序：數據超內存，磁盤順序讀寫，歸併是首選。
• 鏈表排序：O(1) 空間，只需調整指針（如 JDK LinkedList.sort()）。
• 穩定排序需求：多關鍵字排序（先按次關鍵字排序，再按主關鍵字穩定排序）。
• 倒序對統計：合併過程中自然計算逆序對數量。

總結

歸併排序是唯一兼具 O(n log n) 最壞時間、穩定性、順序訪問特性的通用排序算法。雖需 O(n) 空間，但在對象排序、外部排序、並行計算等領域不可替代。Java 標準庫對象數組排序（TimSort）即基於歸併與插入排序混合優化而成。