排序与查找
归并排序
归并排序是经典的分治算法：把列表对半切开，分别给每一半排序（用同样的方法递归下去，一直分到单个元素——单个元素天然有序），然后把两段已排序的半截再合并成一个有序的整体。巧妙之处全在合并这一步——把两段本已有序的列表拼起来很容易，因为你只要不断从两段的最前端里取较小的那个就行。
想象合并两摞正面朝上、各自有序的牌：看两摞最上面的牌，取较小的那张，重复；输出的那一摞就完美有序了。因为每次切分都把问题对半，递归大约有 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)。
又称
另见