排序與搜尋
合併排序
合併排序是經典的分治演算法：把清單對半切開，分別給每一半排序（用同樣的方法遞迴下去，一直分到單個元素——單個元素天然有序），然後把兩段已排序的半截再合併成一個有序的整體。巧妙之處全在合併這一步——把兩段本已有序的清單拼起來很容易，因為你只要不斷從兩段的最前端裡取較小的那個就行。
想像合併兩疊正面朝上、各自有序的牌：看兩疊最上面的牌，取較小的那張，重複；輸出的那一疊就完美有序了。因為每次切分都把問題對半，遞迴大約有 log(n) 層深；而在每一層上，跨越所有碎片的合併都會把每個元素碰一次——每層的工作量是 n。
兩者相乘就得到 O(n log n) 的時間——關鍵是，這在最好、平均、最壞情況下都一樣成立；合併排序沒有「壞輸入」。代價是記憶體：合併這一步需要一塊暫存緩衝區，所以它要用 O(n) 的額外空間，而不是完全原地排序。它是穩定的（當出現相等的鍵、且並列時優先取左半段，相等鍵保持原序），因此在看重穩定性、以及要對大到放不進記憶體的資料排序時（外部合併排序），它都很受青睞。
void merge(std::vector<int>& a, int lo, int mid, int hi) {
std::vector<int> tmp;
int i = lo, j = mid + 1;
while (i <= mid && j <= hi)
tmp.push_back(a[i] <= a[j] ? a[i++] : a[j++]); // <= keeps it stable
while (i <= mid) tmp.push_back(a[i++]);
while (j <= hi) tmp.push_back(a[j++]);
for (int k = 0; k < (int)tmp.size(); ++k) a[lo + k] = tmp[k];
}合併總長為 n 的兩段有序半截是 O(n)；跨 log n 層做完便是 O(n log n)。
合併排序的 O(n log n) 對任何輸入都成立——不會像快速排序那樣出現最壞情況的爆炸。換取這份保證的代價就是那塊 O(n) 的輔助陣列。它的遞迴式 T(n) = 2T(n/2) + O(n) 由主定理解出 O(n log n)。
又稱
另見