揭秘合併排序：分治排序初學者指南

歸併排序由約翰·馮·諾依曼於 1945 年提出，主要是為了提高大型資料集的排序效率。馮·諾依曼的演算法旨在使用分而治之的方法提供一致且可預測的排序過程。這種策略允許歸併排序有效地處理小型和大型資料集，保證在所有情況下都能實現穩定的排序，時間複雜度為 O(n log n)。

合併排序採用分而治之方法，將數組分割成更小的子數組，對它們進行遞歸排序，然後將排序後的數組重新合併在一起。這種方法將問題分解為可管理的區塊，對每個區塊進行單獨排序並有效地將它們組合起來。因此，透過劃分排序工作量，該演算法即使在大型資料集上也能表現良好。

遞歸是一個函數呼叫自身來解決同一問題的較小版本的過程。它不斷分解問題，直到問題足夠簡單可以直接解決，稱為基本情況。

以下是 JavaScript 中歸併排序的實現，展示如何遞歸地拆分和合併數組：

function mergeSort(arr) {
    if (arr.length <= 1) return arr;

    const mid = Math.floor(arr.length / 2);
    const left = mergeSort(arr.slice(0, mid));
    const right = mergeSort(arr.slice(mid));

    return merge(left, right);
}

function merge(left, right) {
    let result = [];
    while (left.length && right.length) {
        if (left[0] < right[0]) result.push(left.shift());
        else result.push(right.shift());
    }
    return result.concat(left, right);
}

為了更好地理解歸併排序的工作原理，讓我們使用數組來演示整個過程：[38, 27, 43, 3, 9, 82, 10]

第 1 步：遞歸除法（mergeSort 函數）
這個數組被遞歸地分割成更小的子數組，直到每個子數組只有一個元素。這是透過 mergeSort 函數中的以下幾行實現的：

function mergeSort(arr) {
    if (arr.length <= 1) return arr;

這會停止我們的遞歸。

以下是遞歸除法的展開方式：

• 初始呼叫: mergeSort([38, 27, 43, 3, 9, 82, 10])
  • 數組在中點分割： [38,27,43] 和 [3,9,82,10]

• 上半場：

  • 合併排序([38,27,43])
    • 在中點分割：[38] 和 [27, 43]
  • 合併排序([27, 43])
    • 分為[27]和[43]
  • 子數組 [38]、[27] 和 [43] 現在是單獨的元素，可以合併。

• 下半場：

  • 合併排序([3, 9, 82, 10])
    • 在中點分割：[3, 9] 和 [82, 10]
  • 合併排序([3, 9])
    • 分為[3]和[9]
  • 合併排序([82, 10])
    • 分為[82]和[10]
  • 子數組 [3]、[9]、[82] 和 [10] 現在已準備好合併。

第 2 步：合併已排序的子數組（合併函數）
現在，我們開始使用 merge 函數將子數組按排序順序合併在一起：

function merge(left, right) {
    let result = [];
    while (left.length && right.length) {
        if (left[0] < right[0]) result.push(left.shift());
        else result.push(right.shift());
    }
    return result.concat(left, right);
}

合併過程的工作原理如下：

第一次合併（來自基本情況）：

• 合併 [27] 和 [43] → 結果為 [27, 43]
• 將 [38] 與 [27, 43] 合併 → 結果為 [27, 38, 43]

此時，陣列的左半部已完全合併：[27, 38, 43]。

第二次合併（來自基本情況）：

• 合併 [3] 和 [9] → 結果為 [3, 9]
• 合併 [82] 和 [10] → 結果為 [10, 82]
• 將 [3, 9] 與 [10, 82] 合併 → 結果為 [3, 9, 10, 82]

現在，右半部已完全合併：[3, 9, 10, 82]。

第 3 步：最終合併
最後，使用 merge 函數將兩半 [27, 38, 43] 和 [3, 9, 10, 82] 合併：

比較 27（左[0]）和 3（右[0]）。由於 3 比較 27 和 9。將結果加上 9。
比較 27 和 10。結果加 10。
比較 27 和 82。將結果加上 27。
比較 38 和 82。結果加上 38。
比較 43 和 82。將 43 加到結果中。
新增右側數組中剩餘的元素 82。
完全合併和排序的陣列是：
[3, 9, 10, 27, 38, 43, 82].

時間複雜度： 最佳、平均和最壞情況：O(n log n)
讓我們仔細看看：

除法（O(log n)）：每次將陣列分成兩半，問題的大小就會減少。由於數組在每一步都被分成兩半，因此執行此操作的次數與 log n 成正比。例如，如果有 8 個元素，則可以將它們分成兩半 3 次（因為 log2(8) = 3）。

合併（O(n)）：分割數組後，演算法將較小的數組依序合併在一起。合併兩個大小為 n 的排序數組需要 O(n) 時間，因為您必須對每個元素進行一次比較和組合。

整體複雜度（O(n log n)）：由於除法需要O(log n) 步驟，並且在每一步合併n 個元素，因此總時間複雜度是這兩者的乘積：O(n log n)。

空間複雜度： O(n)
合併排序需要與數組大小成正比的額外空間，因為它在合併階段需要臨時數組來儲存元素。

與其他排序演算法的比較：
快速排序：雖然快速排序的平均時間複雜度為 O(n log n)，但最壞的情況可能是 O(n^2)。合併排序避免了這種最壞的情況，但當空間受到關注時，快速排序對於記憶體中排序通常更快。
冒泡排序：比合併排序效率低很多，平均和最壞情況的時間複雜度為 O(n^2)。

真實世界用法
合併排序廣泛用於外部排序，其中需要從磁碟對大型資料集進行排序，因為它可以有效地處理無法放入記憶體的資料。它也通常在平行計算環境中實現，其中子數組可以利用多核心處理進行獨立排序。

此外，Python (Timsort)、Java 和C (std::stable_sort) 等函式庫和語言都依賴合併排序的變體來確保排序操作的穩定性，使其特別適合對物件和複雜資料結構進行排序。

結論
由於其穩定性、一致的性能以及對大型資料集排序的適應性，合併排序仍然是理論計算機科學和實際應用中的基本演算法。雖然QuickSort 等其他演算法在某些情況下可能執行得更快，但合併排序保證的O(n log n) 時間複雜度和多功能性使其對於記憶體受限的環境以及維護具有相同鍵的元素的順序非常有價值。它在現代編程庫中的作用確保了它在現實世界的應用程式中保持相關性。

資料來源：

1. Knuth，Donald E. 電腦程式設計藝術，卷。 3：排序和搜尋。 Addison-Wesley Professional，1997 年，第 158-160 頁。
2. Cormen，Thomas H. 等。算法簡介。麻省理工學院出版社，2009 年，第 2 章（歸併排序）、第 5 章（演算法複雜性）、第 7 章（快速排序）。
3. Silberschatz、亞伯拉罕等人。資料庫系統概念。 McGraw-Hill，2010 年，第 13 章（外部排序）。
4. 「提姆索特。」 Python 文件、Python 軟體基礎。 Python 的 Timsort
5. 「Java 陣列.排序」。 Oracle 文檔。 Java 的 Arrays.sort()

以上是揭秘合併排序：分治排序初學者指南的詳細內容。更多資訊請關注PHP中文網其他相關文章！