分治法的三步模板（divide-conquer-combine）

想像你要徒手把一大箱紙本表格按字母順序排好。一次處理全部讓人崩潰，於是你把箱子分成兩半，各交給一位朋友，請他們用同樣的方法把自己那半排好。當兩半都排好回來時，你只要把它們交錯併成一疊就完成了。這種直覺——把工作切成幾塊、各塊分別解決、再把答案縫合起來——就是分治法（divide and conquer）模板，也是設計快速遞迴演算法最常見的方式。

精確地說，這個模板有三個步驟。分解（divide）：把規模為 n 的問題切成 a 個（通常是 2 個）子問題，每個規模約為 n/b（通常是 n/2）。征服（conquer）：對每個子問題遞迴呼叫同一個程序來解；遞迴在小到能直接解決的基底情形（base case）停下（例如只有一個元素的陣列本來就排好了）。合併（combine）：把各子問題的答案組裝成原問題的答案。以合併排序處理 [3,1,2,4] 做個小追蹤：分解成 [3,1] 與 [2,4]；遞迴征服得到 [1,3] 與 [2,4]；合併兩者得到 [1,2,3,4]。其成本由遞迴關係式描述，例如 T(n) = 2 T(n/2) + O(n)，其中 O(n) 就是合併的工作量。

分治法之所以重要，是因為當合併步驟便宜時，對半切分能把執行時間壓到 O(n log n) 甚至更好，勝過許多直接方法的 O(n^2)。它驅動了合併排序、快速排序、二分搜尋、快速乘法、快速傅立葉轉換（FFT）以及線性時間選擇。必須遵守的一條規則是：子問題應該真正彼此獨立——解其中一個不能依賴於已先解了另一個。當子問題重疊、你會把同一個子問題重算許多次時，單純的分治法就很浪費，這時應改用動態規劃。