歸併排序是基於“分而治之”（Divide and Conquer）思想的經典排序算法，非常適合初學者理解分治策略與遞歸的結合。它通過將複雜問題拆解爲簡單子問題，解決後再合併結果，最終實現高效排序。
一、分治思想：從“大問題”到“小問題”¶
“分治”的核心是 “分而治之”：將一個大問題拆分成多個小問題，逐個解決後，再將結果合併。
舉個生活例子：整理一堆雜亂的撲克牌。
1. 分：把52張牌分成兩堆（26張），再把每堆分成更小的兩堆（13張），直到每堆只剩1張（天然有序）。
2. 治：將最小的牌堆（1張）按大小合併成兩堆（2張），再合併成4張、8張……最終合併成完整的有序牌堆。
類比到數組排序：將數組分成兩半，遞歸排序每一半，最後合併成一個有序數組。
二、歸併排序的核心步驟¶
歸併排序分爲 “分解（Divide）” 和 “合併（Merge）” 兩步：
1. 分解（Divide）：遞歸拆分數組¶
- 如果數組長度 ≤ 1，直接返回（單個元素已有序）。
- 否則，找到數組中間位置
mid，拆分爲左半部分left和右半部分right。 - 遞歸分解左半部分和右半部分，直到子數組長度爲1。
示例：數組 [5, 3, 8, 6, 2, 7, 1, 4]
- 第一次分解：中間位置 mid = 3，拆分爲 left = [5,3,8,6] 和 right = [2,7,1,4]。
- 遞歸分解 left 和 right，直到所有子數組長度爲1：[5], [3], [8], [6], [2], [7], [1], [4]。
2. 合併（Merge）：合併有序子數組¶
當子數組分解到長度爲1後，開始合併相鄰的有序子數組。合併時需確保結果有序：
- 用兩個指針 i 和 j 分別指向兩個子數組的起始位置。
- 比較 i 和 j 指向的元素，將較小的元素放入臨時數組，移動對應指針。
- 重複直到一個子數組遍歷完畢，將剩餘元素直接放入臨時數組。
- 最後將臨時數組複製回原數組。
合併過程示例：
合併 [5] 和 [3]：
- 指針 i=0（指向 5），j=0（指向 3）。
- 比較：3 < 5，放入臨時數組 → [3]，j=1（右子數組遍歷完畢）。
- 剩餘元素 [5] 直接放入 → 臨時數組 [3,5]，複製回原數組，得到 [3,5]。
三、歸併排序完整流程（以數組 [5,3,8,6,2,7,1,4] 爲例）¶
- 分解：遞歸拆分爲 8 個長度爲1的子數組。
- 合併第一層：兩兩合併，得到 4 個有序子數組：
[3,5],[6,8],[2,7],[1,4]。 - 合併第二層：繼續合併，得到 2 個有序子數組：
[3,5,6,8],[1,2,4,7]。 - 合併最終層：合併上述兩數組，得到完整有序數組
[1,2,3,4,5,6,7,8]。
四、時間複雜度與空間複雜度¶
- 時間複雜度：分解的遞歸深度爲
O(log n)（每次分解規模減半），每層合併需遍歷所有元素（O(n)），總時間複雜度爲O(n log n)（無論數組初始順序如何，時間複雜度穩定）。 - 空間複雜度：合併過程需臨時數組存儲結果，額外空間爲
O(n)。
五、穩定性：歸併排序的優勢¶
歸併排序是 穩定排序：合併時若兩個子數組出現相等元素（如 [2,2]），會優先取左邊子數組的元素，不改變相等元素的相對順序。
總結¶
歸併排序通過“分治”思想將複雜排序問題簡化爲子問題，核心是 “分解-遞歸-合併”。它直觀體現瞭如何將大問題拆解爲可解決的小問題，是理解分治算法的絕佳案例。儘管需要額外空間，但時間複雜度穩定在 O(n log n)，適合處理大數據量或需要穩定排序的場景。
歸併排序的原理清晰、步驟明確，通過本文的示例和講解，相信你已能輕鬆掌握它的核心邏輯！