归并排序定义归并排序（merge sort）是高效的基于比较的稳定排序算法．
性质归并排序基于分治思想将数组分段排序后合并，时间复杂度在最优、最坏与平均情况下均为 Θ(𝑛log𝑛)Θ(nlogn)，空间复杂度为 Θ(𝑛)Θ(n)．
归并排序可以只使用 Θ(1)Θ(1) 的辅助空间，但为便捷通常使用与原数组等长的辅助数组．
过程合并归并排序最核心的部分是合并（merge）过程：将两个有序的数组 a[i] 和 b[j] 合并为一个有序数组 c[k]．
从左往右枚举 a[i] 和 b[j]，找出最小的值并放入数组 c[k]；重复上述过程直到 a[i] 和 b[j] 有一个为空时，将另一个数组剩下的元素放入 c[k]．
为保证排序的稳定性，前段首元素小于或等于后段首元素时（a[i] <= b[j]）而非小于时（a[i] < b[j]）就要作为最小值放入 c[k]．
实现C/C++Python数组实现指针实现 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16void merge(const int *a, size_t aLen, const int *b, size_t bLen, int *c) {
size_t i = 0, j = 0, k = 0;
while (i < aLen && j < bLen) {
if (b[j] < a[i]) { // 先判断 b[j] < a[i]，保证稳定性
c[k] = b[j];
++j;
} else {
c[k] = a[i];
++i;
}
++k;
}
// 此时一个数组已空，另一个数组非空，将非空的数组并入 c 中
for (; i < aLen; ++i, ++k) c[k] = a[i];
for (; j < bLen; ++j, ++k) c[k] = b[j];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15void merge(const int *aBegin, const int *aEnd, const int *bBegin,
const int *bEnd, int *c) {
while (aBegin != aEnd && bBegin != bEnd) {
if (*bBegin < *aBegin) {
*c = *bBegin;
++bBegin;
} else {
*c = *aBegin;
++aBegin;
}
++c;
}
for (; aBegin != aEnd; ++aBegin, ++c) *c = *aBegin;
for (; bBegin != bEnd; ++bBegin, ++c) *c = *bBegin;
}
也可使用
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15def merge(a, b):
i, j = 0, 0
c = []
while i < len(a) and j < len(b):
# 先判断 b[j] < a[i]，保证稳定性
if b[j] < a[i]:
c.append(b[j])
j += 1
else:
c.append(a[i])
i += 1
# 此时一个数组已空，另一个数组非空，将非空的数组并入 c 中
c.extend(a[i:])
c.extend(b[j:])
return c
分治法实现归并排序当数组长度为 11 时，该数组就已经是有序的，不用再分解．
当数组长度大于 11 时，该数组很可能不是有序的．此时将该数组分为两段，再分别检查两个数组是否有序（用第 1 条）．如果有序，则将它们合并为一个有序数组；否则对不有序的数组重复第 2 条，再合并．
用数学归纳法可以证明该流程可以将一个数组转变为有序数组．
为保证排序的复杂度，通常将数组分为尽量等长的两段（𝑚𝑖𝑑 =⌊𝑙+𝑟2⌋mid=⌊l+r2⌋）．
实现注意下面的代码所表示的区间分别是 [𝑙,𝑟)[l,r)，[𝑙,𝑚𝑖𝑑)[l,mid)，[𝑚𝑖𝑑,𝑟)[mid,r)．
C/C++Python 1
2
3
4
5
6
7
8
9
10
11void merge_sort(int *a, int l, int r) {
if (r - l <= 1) return;
// 分解
int mid = l + ((r - l) >> 1);
merge_sort(a, l, mid), merge_sort(a, mid, r);
// 合并
int tmp[1024] = {}; // 请结合实际情况设置 tmp 数组的长度（与 a 相同），或使用
// vector；先将合并的结果放在 tmp 里，再返回到数组 a
merge(a + l, a + mid, a + mid, a + r, tmp + l); // pointer-style merge
for (int i = l; i < r; ++i) a[i] = tmp[i];
}
1
2
3
4
5
6
7
8
9def merge_sort(a, ll, rr):
if rr - ll <= 1:
return
# 分解
mid = (rr + ll) // 2
merge_sort(a, ll, mid)
merge_sort(a, mid, rr)
# 合并
a[ll:rr] = merge(a[ll:mid], a[mid:rr])
倍增法实现归并排序已知当数组长度为 11 时，该数组就已经是有序的．
将数组全部切成长度为 11 的段．
从左往右依次合并两个长度为 11 的有序段，得到一系列长度 ≤2≤2 的有序段；
从左往右依次合并两个长度 ≤2≤2 的有序段，得到一系列长度 ≤4≤4 的有序段；
从左往右依次合并两个长度 ≤4≤4 的有序段，得到一系列长度 ≤8≤8 的有序段；
……
重复上述过程直至数组只剩一个有序段，该段就是排好序的原数组．
为什么是 ≤𝑛≤n 而不是 =𝑛=n 数组的长度很可能不是 2𝑥2x，此时在最后就可能出现长度不完整的段，可能出现最后一个段是独立的情况．
实现C/C++Python 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15void merge_sort(int *a, size_t n) {
int tmp[1024] = {}; // 请结合实际情况设置 tmp 数组的长度（与 a 相同），或使用
// vector；先将合并的结果放在 tmp 里，再返回到数组 a
for (size_t seg = 1; seg < n; seg <<= 1) {
for (size_t left1 = 0; left1 < n - seg;
left1 += seg + seg) { // n - seg: 如果最后只有一个段就不用合并
size_t right1 = left1 + seg;
size_t left2 = right1;
size_t right2 = std::min(left2 + seg, n); // 注意最后一个段的边界
merge(a + left1, a + right1, a + left2, a + right2,
tmp + left1); // pointer-style merge
for (size_t i = left1; i < right2; ++i) a[i] = tmp[i];
}
}
}
1
2
3
4
5
6
7
8
9def merge_sort(a):
seg = 1
while seg < len(a):
for l1 in range(0, len(a) - seg, seg + seg):
r1 = l1 + seg
l2 = r1
r2 = l2 + seg
a[l1:r2] = merge(a[l1:r1], a[l2:r2])
seg <<= 1
逆序对相关阅读和参考实现：逆序对
逆序对是 𝑖 <𝑗i
排序后的数组无逆序对．归并排序的合并操作中，每次后段首元素被作为当前最小值取出时，前段剩余元素个数之和即是合并操作减少的逆序对数量；故归并排序计算逆序对数量的时间复杂度为 Θ(𝑛log𝑛)Θ(nlogn)．此外，逆序对计数还可以通过树状数组或线段树解决，时间复杂度也是 𝑂(𝑛log𝑛)O(nlogn)；这一算法的详细解释参见 树状数组 相应描述．两种算法的参考实现都在 逆序对 章节．
外部链接Merge Sort - GeeksforGeeks归并排序 - 维基百科，自由的百科全书逆序对 - 维基百科，自由的百科全书本页面最近更新：2026/1/7 08:56:54，更新历史发现错误？想一起完善？ 在 GitHub 上编辑此页！本页面贡献者：NachtgeistW, Enter-tainer, Tiphereth-A, sshwy, ksyx, Xeonacid, c-forrest, iamtwz, ChungZH, Great-designer, H-J-Granger, invalid-email-address, Ir1d, IronSublimate, Junyan721113, lychees, mcendu, megakite, Menci, minghu6, ouuan, partychicken, SaisycJiang, shawlleyw, untitledunrevised, weisi, zexpp5, ZnPdCo本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用