# 归并排序简介
「归并排序」和「快速排序」是理解「递归」思想的非常好的学习材料。在学习的过程中，可以重点理解：递归完成以后，合并两个有序数组的这一步骤，想清楚程序的执行流程。即：递归函数执行完成以后，我们还可以做点事情。因此，「归并排序」和「快速排序」非常重要，一定要掌握。
归并排序与快速排序都是基于「分治思想」的排序算法。
- 分治思想（分而治之）把一个规模较大的问题拆分成为若干个规模较小的相同类型的子问题，然后对这些子问题递归求解，等待每一个子问题完成以后，再得到原问题的解；
- 分治算法可以并行执行，但是在基础算法领域，分治算法是以 深度优先遍历 的方式执行的。
深刻理解「归并排序」，有助于理解「递归」与「深度优先遍历」。
说明：
- 第 88 题：归并排序，注意这里从后向前归并；
- 《剑指 Offer》第 51 题：归并排序、树状数组（选学）；
- 第 75 题：著名的「荷兰国旗」问题、快排；
- 第 215 题：快排、优先队列；
- 第 451 题：快排、优先队列。
分治思想的典型问题：「剑指 Offer 第 51 题」：《剑指 Offer》 51. 数组中的逆序对（视频讲解） (opens new window)。
| 题号 | 链接 | 题解 |
|---|---|---|
| 50 | Pow(x, n) (opens new window) | 文字题解 (opens new window) |
# 通过「归并排序」和「快速排序」的学习深入理解递归
和排序相关的问题
「归并排序」和「快速排序」是非常重要的排序算法，深刻理解它们对于理解「递归」函数的运行机制有着非常大的帮助，同时它们也是「分治思想」的典型应用。「逆序对」和「荷兰国旗问题（颜色分类）」也是非常经典的算法问题。
| 题目链接 | 力扣 | B 站 |
|---|---|---|
| 《剑指 Offer》 51. 数组中的逆序对（困难） (opens new window) | 力扣 (opens new window) | B 站 (opens new window) |
| 315. 计算右侧小于当前元素的个数（困难） (opens new window) | 力扣 (opens new window) | B 站 (opens new window) |
计算「逆序对」完全就是按照「归并排序」的思路而来。
| 题目链接 | 力扣 | B 站 |
|---|---|---|
| 75. 颜色分类（中等） (opens new window) | 力扣 (opens new window) | B 站 (opens new window) |
在「颜色分类」问题的讲解中，我们向大家介绍了「循环不变量」，在编写代码的过程中，我们应该一直遵守所使用的变量的语义，在「程序执行前」「执行过程中」「执行结束」以后保持不变。遵守我们自己定义「循环不变量」是我们写对正确代码的重要方法。
| 题目链接 | 力扣 | B 站 |
|---|---|---|
| 41. 缺失的第一个正数（困难） (opens new window) | 力扣 (opens new window) | B 站 (opens new window) |
「缺失的第一个正数」是一个经典的算法问题，用到的思想是「原地哈希」，可以理解为是「桶排序」算法的特殊应用：一个萝卜一个坑，一个桶里只存放一个元素。要和大家强调的是，可以这样做是和输入数组的元素的数值密切相关。
作者：liweiwei1419 链接：https://suanfa8.com/merge-sort 来源：算法吧 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。