合併排序原理與 Java 實作完整指南

什麼是合併排序？

合併排序 是一種經典的「分而治之」演算法，屬於穩定排序，時間複雜度固定為 O(n log n)。核心思想是將陣列不斷二分，直到每個子陣列只剩一個元素（天然有序），再將有序子陣列兩兩合併，最終得到完整有序陣列。

演算法步驟圖解

以陣列 [3, 5, 2, 6, 2] 為例：

1. 分割階段：遞迴二分 [3,5,2] / [6,2] → [3,5] / [2] / [6] / [2] → [3] / [5] / [2] / [6] / [2]
2. 合併階段：[3]+[5]→[3,5] → [3,5]+[2]→[2,3,5] → [6]+[2]→[2,6] → [2,3,5]+[2,6]→[2,2,3,5,6]

核心合併邏輯

合併兩個有序陣列 left[low..mid] 與 right[mid+1..high]：

1. 申請暫存陣列 temp[high-low+1]
2. 雙指標 i=low、j=mid+1，比較元素大小，較小者放入 temp
3. 其中一陣列耗盡後，將另一陣列剩餘元素直接複製入 temp
4. 將 temp 複製回原陣列對應區間

Java 完整實作（含過程輸出）

package com.coder4j.main.arithmetic.sorting;

public class MergeSort {

    private static int step = 0;

    public static int[] sort(int[] array) {
        if (array == null || array.length <= 1) return array;
        return sort(array, 0, array.length - 1);
    }

    private static int[] sort(int[] array, int low, int high) {
        if (low < high) {
            int mid = (low + high) / 2;
            step++;
            System.out.printf("第 %d 次分割: [%d-%d] [%d-%d]%n", step, low, mid, mid + 1, high);

            sort(array, low, mid);          // 左半部遞迴排序
            sort(array, mid + 1, high);     // 右半部遞迴排序
            merge(array, low, mid, high);   // 合併
        }
        return array;
    }

    private static void merge(int[] array, int low, int mid, int high) {
        System.out.printf("合併: [%d-%d] 和 [%d-%d]%n", low, mid, mid + 1, high);

        int[] temp = new int[high - low + 1];
        int i = low, j = mid + 1, k = 0;

        // 雙指標合併
        while (i <= mid && j <= high) {
            temp[k++] = (array[i] <= array[j]) ? array[i++] : array[j++];
        }
        while (i <= mid) temp[k++] = array[i++];
        while (j <= high) temp[k++] = array[j++];

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

    public static void main(String[] args) {
        int[] data = {3, 5, 2, 6, 2};
        System.out.println("原始陣列: " + Arrays.toString(data));
        int[] sorted = sort(data);
        System.out.println("排序結果: " + Arrays.toString(sorted));
    }
}

執行輸出範例

原始陣列: [3, 5, 2, 6, 2]
第 1 次分割: [0-2] [3-4]
第 2 次分割: [0-1] [2-2]
第 3 次分割: [0-0] [1-1]
合併: [0-0] 和 [1-1]
合併: [0-1] 和 [2-2]
第 4 次分割: [3-3] [4-4]
合併: [3-3] 和 [4-4]
合併: [0-2] 和 [3-4]
排序結果: [2, 2, 3, 5, 6]

複雜度與特性總結

優化方向

• 小陣列改用插入排序：當子陣列長度 < 閾值（如 16）時，改用插入排序減少遞迴開銷。
• 避免重複分配陣列：在最外層分配一個全域暫存陣列，遞迴傳遞重複使用。
• 就地合併：進階技巧可減少空間到 O(1)，但實作複雜且常數因子大，實務較少用。

結語

合併排序以穩定的 O(n log n) 表現與簡潔的遞迴結構，成為教學與工業級排序（如 Java Arrays.sort() 物件版、Python sorted()）的首選演算法。理解其分割與合併的雙階段機制，是掌握分治法的關鍵入門。