归并排序

基础知识 / merge-sort

本地源文件：docs/basic__merge-sort.md

归并排序

定义

归并排序（merge sort）是高效的基于比较的稳定排序算法．

性质

归并排序基于分治思想将数组分段排序后合并，时间复杂度在最优、最坏与平均情况下均为 Θ(𝑛log⁡𝑛)Θ(nlog⁡n)，空间复杂度为 Θ(𝑛)Θ(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

数组实现指针实现

---|---

---|---

也可使用 <algorithm> 库的 merge 函数，用法与上述指针式写法的相同．

---|---

### 分治法实现归并排序

  1. 当数组长度为 11![](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7) 时，该数组就已经是有序的，不用再分解．

  2. 当数组长度大于 11![](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7) 时，该数组很可能不是有序的．此时将该数组分为两段，再分别检查两个数组是否有序（用第 1 条）．如果有序，则将它们合并为一个有序数组；否则对不有序的数组重复第 2 条，再合并．

用数学归纳法可以证明该流程可以将一个数组转变为有序数组．

为保证排序的复杂度，通常将数组分为尽量等长的两段（𝑚𝑖𝑑 =⌊𝑙+𝑟2⌋mid=⌊l+r2⌋![](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)）．

#### 实现

注意下面的代码所表示的区间分别是 [𝑙,𝑟)[l,r)![](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)，[𝑙,𝑚𝑖𝑑)[l,mid)![](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)，[𝑚𝑖𝑑,𝑟)[mid,r)![](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)．

C/C++Python

---|---

---|---

### 倍增法实现归并排序

已知当数组长度为 11![](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7) 时，该数组就已经是有序的．

将数组全部切成长度为 11![](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7) 的段．

从左往右依次合并两个长度为 11![](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7) 的有序段，得到一系列长度 ≤2≤2![](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7) 的有序段；

从左往右依次合并两个长度 ≤2≤2![](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7) 的有序段，得到一系列长度 ≤4≤4![](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7) 的有序段；

从左往右依次合并两个长度 ≤4≤4![](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7) 的有序段，得到一系列长度 ≤8≤8![](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7) 的有序段；

……

重复上述过程直至数组只剩一个有序段，该段就是排好序的原数组．

为什么是 ≤𝑛≤n![](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7) 而不是 =𝑛=n![](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)

数组的长度很可能不是 2𝑥2x![](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)，此时在最后就可能出现长度不完整的段，可能出现最后一个段是独立的情况．

#### 实现

C/C++Python

---|---

---|---

## 逆序对

相关阅读和参考实现：[逆序对](../../math/permutation/#逆序数)

逆序对是 𝑖 <𝑗i<j![](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7) 且 𝑎𝑖 >𝑎𝑗ai>aj![](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7) 的有序数对 (𝑖,𝑗)(i,j)![](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)．

排序后的数组无逆序对．归并排序的合并操作中，每次后段首元素被作为当前最小值取出时，前段剩余元素个数之和即是合并操作减少的逆序对数量；故归并排序计算逆序对数量的时间复杂度为 Θ(𝑛log⁡𝑛)Θ(nlog⁡n)![](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)．此外，逆序对计数还可以通过树状数组或线段树解决，时间复杂度也是 𝑂(𝑛log⁡𝑛)O(nlog⁡n)![](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)；这一算法的详细解释参见 [树状数组](../../ds/fenwick/#全局逆序对全局二维偏序) 相应描述．两种算法的参考实现都在 [逆序对](../../math/permutation/#逆序数) 章节．

## 外部链接

  * [Merge Sort - GeeksforGeeks](https://www.geeksforgeeks.org/merge-sort/)
  * [归并排序 - 维基百科，自由的百科全书](https://zh.wikipedia.org/wiki/%E5%BD%92%E5%B9%B6%E6%8E%92%E5%BA%8F)
  * [逆序对 - 维基百科，自由的百科全书](https://zh.wikipedia.org/wiki/%E9%80%86%E5%BA%8F%E5%AF%B9)

* * *

>  __本页面最近更新： 2026/1/7 08:56:54，[更新历史](https://github.com/OI-wiki/OI-wiki/commits/master/docs/basic/merge-sort.md)
>  __发现错误？想一起完善？[在 GitHub 上编辑此页！](https://oi-wiki.org/edit-landing/?ref=/basic/merge-sort.md "edit.link.title")
>  __本页面贡献者：[NachtgeistW](https://github.com/NachtgeistW), [Enter-tainer](https://github.com/Enter-tainer), [Tiphereth-A](https://github.com/Tiphereth-A), [sshwy](https://github.com/sshwy), [ksyx](https://github.com/ksyx), [Xeonacid](https://github.com/Xeonacid), [c-forrest](https://github.com/c-forrest), [iamtwz](https://github.com/iamtwz), [ChungZH](https://github.com/ChungZH), [Great-designer](https://github.com/Great-designer), [H-J-Granger](https://github.com/H-J-Granger), [invalid-email-address](https://github.com/invalid-email-address), [Ir1d](https://github.com/Ir1d), [IronSublimate](https://github.com/IronSublimate), [Junyan721113](https://github.com/Junyan721113), [lychees](https://github.com/lychees), [mcendu](https://github.com/mcendu), [megakite](https://github.com/megakite), [Menci](https://github.com/Menci), [minghu6](https://github.com/minghu6), [ouuan](https://github.com/ouuan), [partychicken](https://github.com/partychicken), [SaisycJiang](https://github.com/SaisycJiang), [shawlleyw](https://github.com/shawlleyw), [untitledunrevised](https://github.com/untitledunrevised), [weisi](https://github.com/weisi), [zexpp5](https://github.com/zexpp5), [ZnPdCo](https://github.com/ZnPdCo)
>  __本页面的全部内容在**[CC BY-SA 4.0](https://creativecommons.org/licenses/by-sa/4.0/deed.zh) 和 [SATA](https://github.com/zTrix/sata-license)** 协议之条款下提供，附加条款亦可能应用