归并排序 Merge Sort
归并排序 · 稳定的 O(n log n)
什么是归并排序
归并排序的核心是合并两个有序序列：两个都已排好的小段，用两个指针从头比较、每次取较小的放进结果，就能线性地拼成一个更大的有序段。把这个「合并」反复用到底，整个数组就有序了。它是稳定的 O(n log n) 排序，代价是需要一块和原数组等大的辅助空间。
它怎么做
本页用自底向上的写法：段宽 width 从 1 开始，把相邻的两段合并成一段，宽度 1 → 2 → 4 → 8… 一轮轮翻倍，直到覆盖整个数组。点「下一步」看 [7, 6, 5, 10, 9, 8, 4, 3, 2, 1]：下方的 辅助轨（temp）展示当前合并——两段比较、较小者依次填入 temp，填满后整段拷回主轨（柱子平滑重排）。
width=1：合并相邻 1 元素段
1function mergeSort(a: number[]): number[] {
2 const n = a.length;
3 const temp = new Array(n);
4 for (let width = 1; width < n; width *= 2) {
5 for (let lo = 0; lo < n; lo += 2 * width) {
6 const mid = Math.min(lo + width, n);
7 const hi = Math.min(lo + 2 * width, n);
8 let i = lo, j = mid, k = lo;
9 while (i < mid && j < hi) {
10 if (a[i] <= a[j]) {
11 temp[k++] = a[i++];
12 } else {
13 temp[k++] = a[j++];
14 }
15 }
16 while (i < mid) temp[k++] = a[i++];
17 while (j < hi) temp[k++] = a[j++];
18 for (let t = lo; t < hi; t++) a[t] = temp[t];
19 }
20 }
21 return a;
22}
n10
width1
lo-
mid-
hi-
i-
j-
k-
a[i]-
a[j]-
writeCount0
1 / 78
复杂度与适用
时间稳定 O(n log n)（不受输入分布影响）、额外空间 O(n)、稳定。它是「稳定 + 最坏也 O(n log n)」时的首选，也是外部排序（数据大到放不进内存、多路归并磁盘文件）和链表排序的基础。代价是那块辅助内存——这也是它和原地的快排/堆排最大的权衡点。
两种写法，同一个 merge：本页是自底向上（迭代、段宽翻倍）；自顶向下归并页是递归分治（对半下钻、回程合并，配调用栈看）。合并过程一模一样，只是驱动方式不同。
想看递归版怎么用「分治 + 调用栈」组织同一个合并，去自顶向下归并页对照——两页并看，「归并」就彻底通了。