合併排序作為分治法（merge sort）

合併排序是分治法的教科書範例，日常的畫面正是那個整箱表格的故事：要排好一疊，就把它對半切，用同樣方法各排一半，再把兩個已排序的半疊合併成一疊。它持續切分，直到每塊只剩一張卡片——那本來就已排序——然後在回程上做真正的工作，把小的已排序段落合併成更大的段落。

對 [5,2,4,1] 一步步來：分解成 [5,2] 與 [4,1]。遞迴：[5,2] 分成 [5] 與 [2]，合併成 [2,5]；[4,1] 分成 [4] 與 [1]，合併成 [1,4]。合併：用雙指標掃描合併 [2,5] 與 [1,4]——取 1、取 2、取 4、取 5——得到 [1,2,4,5]。合併總長為 n 的兩個已排序串列只需單趟線性掃描，所以合併花 O(n)，遞迴關係式為 T(n) = 2 T(n/2) + O(n)。可用對遞迴呼叫的歸納法證明正確性：單元素陣列已排序（基底情形），若兩次遞迴呼叫都回傳正確排序的半段，合併步驟可證明會依序輸出它們，於是整個結果都已排序。

解 T(n) = 2 T(n/2) + O(n) 在最壞、最好、平均情況下都得到 O(n log n)——合併排序永遠不會退化成 O(n^2)，這是它相對於樸素快速排序的一大優勢。它也是穩定的（相等的鍵維持原本順序）且循序合併，因此是排序磁碟上資料或鏈結串列的首選。代價是空間：標準合併需要一個 O(n) 的輔助陣列，所以它不是原地排序。這個記憶體成本，正是儘管快速排序的最壞情況較差，記憶體內的陣列排序通常仍偏好快速排序的常見原因。