又快又穩的排序法 —— 一直對半切到剩一個,再把排好的小段兩兩合併回去。
分(Divide) —— 把大問題對半切成兩個小問題。
治(Conquer) —— 分別把兩個小段排好(通常靠遞迴,一直切到剩一個)。
合(Combine) —— 把兩個已排序的小段合併成一個大的排序段。這一步是整個演算法的心臟。
[38, 27, 43, 3]
╱ ╲ ← 分:對半切
[38, 27] [43, 3]
╱ ╲ ╱ ╲
[38] [27] [43] [3] ← 切到剩一個
╲ ╱ ╲ ╱
[27, 38] [3, 43] ← 合:兩兩合併
╲ ╱
[3, 27, 38, 43] ← 合回完整排序
<= 決定誰先拿,鍵相同會保留原順序。同樣一批資料,差距非常明顯:
資料越大,差距越誇張——這就是 O(n log n) 打敗 O(n²) 的威力。
下面有兩個已經排好序的清單。合併的規則超簡單:兩邊各派一個指標指著開頭,誰小就先拿誰,拿完往後移。按「下一步」自己走一遍,你就懂 merge 了。
從完整的合併排序、心臟 merge,到逆序對、自底向上、合併多清單等應用。
❌ 忘了「合併」需要兩邊都已排序 —— merge 的前提是左右兩段各自排好,順序才對。
❌ 合併後忘了接尾巴 —— 其中一邊先拿完時,要把另一邊剩下的直接接上去(extend),不能漏掉。
❌ 想省空間就地做 —— 合併排序天生要額外陣列(O(n) 空間)。要 O(1) 空間請改用其他排序。
[1, 4] 和 [2, 3],寫出每一步「拿了誰」,最後結果是什麼?O(n log n),不像快速排序有最壞情況?<= 改成 <,排序結果會變嗎?那「穩定性」會不會受影響?把答案打到對話裡,我幫你對。