歸並排序深度解析：原理、實現與複雜度分析（Java版）

歸並排序是典型的分治算法，核心思想是「分而治之」：將數組遞歸拆分至單元素，再通過 merge 步驟將兩個有序子數組合併為一個有序數組。本文從合併邏輯、遞歸流程、代碼實現到複雜度分析，全方位剖析該算法。

合併過程圖解

假設有序數組 A（4個元素）與 B（6個元素）合併至數組 C（10個空間），雙指針依次比較並填入較小值，剩餘元素直接追加：

算法流程

1. 分割：遞歸將數組二分，直到子數組長度為 1（天然有序）。
2. 合併：自底向上調用 merge，將兩有序段合併為一有序段。
3. 輔助空間：需額外 O(N) 空間存放臨時數組，這是歸並排序的主要缺點。

Java 完整實現

public void mergeSort(int[] source) {
    int[] workSpace = new int[source.length];
    recMergeSort(source, workSpace, 0, source.length - 1);
}

private void recMergeSort(int[] source, int[] workSpace, int lowerBound, int upperBound) {
    if (lowerBound == upperBound) return;
    int mid = (lowerBound + upperBound) / 2;
    recMergeSort(source, workSpace, lowerBound, mid);         // 排序左半
    recMergeSort(source, workSpace, mid + 1, upperBound);     // 排序右半
    merge(source, workSpace, lowerBound, mid + 1, upperBound); // 合併
}

private void merge(int[] a, int[] workSpace, int lowPtr, int highPtr, int upperBound) {
    int j = 0, lowerBound = lowPtr, mid = highPtr - 1, n = upperBound - lowerBound + 1;
    while (lowPtr <= mid && highPtr <= upperBound) {
        workSpace[j++] = (a[lowPtr] < a[highPtr]) ? a[lowPtr++] : a[highPtr++];
    }
    while (lowPtr <= mid) workSpace[j++] = a[lowPtr++];
    while (highPtr <= upperBound) workSpace[j++] = a[highPtr++];
    for (j = 0; j < n; j++) a[lowerBound + j] = workSpace[j];
}

複雜度分析

• 時間複雜度：最好、最壞、平均均為 O(N log N)。分割層數 log N，每層合併 O(N)。
• 空間複雜度：O(N) 輔助數組。
• 穩定性：穩定排序（相等元素相對順序不變）。

適用場景：大數據量、要求穩定、內存充足的場景；不適用：內存極受限環境（如嵌入式系統）。