Java 實現歸併排序算法：原理圖解與完整代碼

算法思想

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

1. 分解：將數組不斷二分，直到每個子數組只剩 1 個元素（天然有序）。
2. 解決：將兩個有序子數組合併為一個有序數組（歸併操作）。
3. 合併：自底向上逐層合併，最終得到完全有序數組。

時間複雜度：O(n log n)（最好/最壞/平均）。空間複雜度：O(n)（輔助數組）。穩定排序。

圖解過程

以數組 {3, 2, 4, 1} 為例：

分解階段：
{3, 2, 4, 1}
   /       \
{3, 2}    {4, 1}
 /  \      /  \
{3} {2}  {4} {1}

歸併階段：
{3} {2}  ->  {2, 3}
{4} {1}  ->  {1, 4}
{2, 3} {1, 4}  ->  {1, 2, 3, 4}

Java 完整實現

public class MergeSort {

    /** 入口方法 */
    public static void sort(int[] array) {
        if (array == null || array.length < 2) return;
        mergeSort(array, 0, array.length - 1);
    }

    /** 遞歸分解 */
    private static void mergeSort(int[] arr, int left, int right) {
        if (left < right) {
            int mid = left + ((right - left) >> 1); // 防止溢出
            mergeSort(arr, left, mid);
            mergeSort(arr, mid + 1, right);
            merge(arr, left, mid, right);
        }
    }

    /** 合併兩個有序區間 [left, mid] 和 [mid+1, right] */
    private static void merge(int[] arr, int left, int mid, int right) {
        int[] temp = new int[right - left + 1];
        int i = left, j = mid + 1, k = 0;

        // 雙指針比較合併
        while (i <= mid && j <= right) {
            temp[k++] = (arr[i] <= arr[j]) ? arr[i++] : arr[j++]; // <= 保證穩定性
        }
        // 複製剩餘元素
        while (i <= mid) temp[k++] = arr[i++];
        while (j <= right) temp[k++] = arr[j++];

        // 寫回原數組
        System.arraycopy(temp, 0, arr, left, temp.length);
    }

    // 測試
    public static void main(String[] args) {
        int[] arr = {3, 2, 4, 1, 5, 0, -1, 8};
        System.out.println("排序前: " + Arrays.toString(arr));
        sort(arr);
        System.out.println("排序後: " + Arrays.toString(arr));
    }
}

關鍵點解析

優化版：自底向上迭代法（避免遞歸開銷）

public static void sortIterative(int[] arr) {
    int n = arr.length;
    int[] temp = new int[n];
    for (int width = 1; width < n; width <<= 1) { // 子數組寬度 1,2,4,8...
        for (int left = 0; left < n; left += (width << 1)) {
            int mid = Math.min(left + width - 1, n - 1);
            int right = Math.min(left + (width << 1) - 1, n - 1);
            if (mid < right) merge(arr, temp, left, mid, right);
        }
    }
}

private static void merge(int[] arr, int[] temp, int left, int mid, int right) {
    // 同遞歸版 merge 邏輯，但直接使用外部傳入的 temp
    // 合併後寫回 arr
}

應用場景與對比

總結

歸併排序以穩定、固定 O(n log n) 性能著稱，是外部排序和鏈表排序的首選。Java 中 Arrays.sort() 對對象數組使用 TimSort（歸併+插入優化），對基本類型使用雙軸快排。理解歸併核心邏輯有助於掌握分治思想、優化大數據排序及面試高頻考點。