Java 實作合併排序演算法：完整原始碼與原理解析

演算法特性

• 時間複雜度：O(n log n)（最佳/平均/最差皆同）
• 空間複雜度：O(n) 輔助陣列
• 穩定排序：相等元素相對順序不變
• 分治法：遞歸分解 → 合併征服

完整實作代碼

package Utils.Sort;

public class MergeSort implements SortStrategy {
    private Comparable[] bridge; // 合併用暫存陣列

    public void sort(Comparable[] obj) {
        if (obj == null) {
            throw new NullPointerException("The param can not be null!");
        }
        bridge = new Comparable[obj.length];
        mergeSort(obj, 0, obj.length - 1);
        bridge = null; // 釋放參考助 GC
    }

    private void mergeSort(Comparable[] obj, int left, int right) {
        if (left < right) {
            int center = (left + right) / 2;
            mergeSort(obj, left, center);       // 左半遞歸排序
            mergeSort(obj, center + 1, right);  // 右半遞歸排序
            merge(obj, left, center, right);    // 合併兩有序子陣列
        }
    }

    private void merge(Comparable[] obj, int left, int center, int right) {
        int mid = center + 1;      // 右半起始索引
        int third = left;          // 暫存陣列寫入位置
        int tmp = left;            // 記錄合併區間起始

        // 雙指針合併：從左右子陣列取較小者放入 bridge
        while (left <= center && mid <= right) {
            if (obj[left].compareTo(obj[mid]) <= 0) {
                bridge[third++] = obj[left++];
            } else {
                bridge[third++] = obj[mid++];
            }
        }

        // 處理剩餘元素
        while (mid <= right) {
            bridge[third++] = obj[mid++];
        }
        while (left <= center) {
            bridge[third++] = obj[left++];
        }

        // 複製回原陣列
        copy(obj, tmp, right);
    }

    private void copy(Comparable[] obj, int left, int right) {
        while (left <= right) {
            obj[left] = bridge[left];
            left++;
        }
    }
}

關鍵設計細節解析

1. Comparable 介面約束

泛型化排序邏輯，支援所有實作 Comparable 的型別（String、Integer、自訂類別等）。

2. 暫存陣列復用

bridge 於 sort() 入口分配一次，遞歸過程共用，避免重複分配記憶體，排序結束釋放參考。

3. 合併邏輯邊界處理

• left <= center 確保左半包含中心點
• mid = center + 1 右半從中心下一個開始
• compareTo(...) <= 0 使用 `<=` 保證穩定性（左半優先）

4. 索引管理

tmp 記錄合併區間起始，copy() 精確回寫對應範圍，避免覆寫未排序區域。

測試驗證範例

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

與其他排序比較

常見變體

• 自底向上迭代版：避免遞歸呼叫開銷
• 自然合併排序：利用既有有序區段減少合併次數
• 原地合併排序：O(1) 空間但實作複雜且較慢