合併步驟（combine step）

當你的朋友把兩疊各自排好的半疊表格交回來後，你還有事要做：必須把兩疊已排序的紙堆編織成一疊。這個編織就是合併步驟——分治演算法中把已解好的子問題答案組裝成整個問題答案的部分。分解與征服這兩步搶了風頭，但合併步驟通常才是巧思與大部分執行時間預算所在之處。

在機制上，合併在遞迴呼叫回傳之後執行。在合併排序中它就是 Merge 程序：沿著兩個已排序半段各放一根手指，反覆把較小的前端元素複製到輸出，便能以 O(n) 時間、單趟線性掃描產生完全排序的陣列。在最大子陣列演算法中，合併步驟是最巧妙的部分——它從切分點向兩側掃描，找出橫跨邊界的最佳子陣列，那正是兩個遞迴答案看不到的唯一情況。在卡拉楚巴（Karatsuba）乘法中，合併把三個較小的乘積做加法與位移。這一步的成本恰好就是遞迴關係式 T(n) = a T(n/b) + f(n) 中的 f(n) 項，因此它掌控整個演算法跑多快。

合併步驟正是你該集中設計心力之處，因為整體速度往往取決於能否讓它便宜。主定理把這點講得很具體：在 T(n) = 2 T(n/2) + f(n) 下，線性合併 f(n) = O(n) 給出 O(n log n)，但二次合併 f(n) = O(n^2) 給出 O(n^2)，徹底抹去切分的好處。初學者常見的錯誤是寫出慢的合併——例如用巢狀迴圈以 O(n^2) 合併兩個已排序串列，而非 O(n) 的雙指標合併——悄悄地把一個 n log n 演算法變成 n^2。