Merge Sort
归并排序
排序核心时间 O(n log n)空间 O(n)
分治：拆成两半分别排序，再把两个有序数组合并。稳定，时间稳定。
动画
7
2
9
4
1
8
5
3
归并排序：分治拆分，再两两有序合并。
1 / 57
- 默认
讲解
需要稳定性、外部排序、以及「先分后合」的标准范例。
- 01递归把区间对半切开，直到单元素。
- 02合并：两个指针扫左右有序段，取较小者写入。
- 03剩余元素接到后面。
- 04总比较次数稳定在 n log n。
易错点
- 合并需要额外数组，空间 O(n)。
- 中点划分要用 mid，合并区间是闭区间还是半开要统一。
代码
function mergeSort(a) {
if (a.length <= class="text-accent">1) return a;
const m = a.length >> class="text-accent">1;
return merge(mergeSort(a.slice(class="text-accent">0, m)), mergeSort(a.slice(m)));
}
function merge(l, r) {
const out = [];
let i = class="text-accent">0, j = class="text-accent">0;
while (i < l.length && j < r.length)
out.push(l[i] <= r[j] ? l[i++] : r[j++]);
return out.concat(l.slice(i), r.slice(j));
}