歸并排序（Merge Sort）原理詳解

歸并排序是一種基于分治法（Divide and Conquer）的高效排序算法，由馮·諾依曼于1945年提出。它的核心思想是將大問題分解為小問題，解決小問題后再合并結果。

核心原理

1. 分治策略（Divide and Conquer）

• 分（Divide）：將無序數組遞歸地拆分成更小的子數組，直到每個子數組只有一個元素（此時可視為已排序）
• 治（Conquer）：將相鄰的有序子數組合并成更大的有序數組
• 合（Combine）：重復合并過程，直到整個數組有序

2. 合并過程（關鍵步驟）

合并兩個已排序的子數組 [left…mid] 和 [mid+1…right]：

1. 創建臨時數組存放合并結果
2. 使用兩個指針分別指向兩個子數組的起始位置
3. 比較指針所指元素，將較小的元素放入臨時數組
4. 移動指針，重復比較過程
5. 將剩余元素直接復制到臨時數組末尾
6. 將臨時數組復制回原數組對應位置

算法步驟詳解

1. 遞歸分解：

   • 計算中點 mid