拓展：归并排序详解及应用
原创约 6948 字
本文讲解的例题
| LeetCode | 力扣 | 难度 |
|---|---|---|
| 315. Count of Smaller Numbers After Self | 315. 计算右侧小于当前元素的个数 | 🔴 |
| 327. Count of Range Sum | 327. 区间和的个数 | 🔴 |
| 493. Reverse Pairs | 493. 翻转对 | 🔴 |
| 912. Sort an Array | 912. 排序数组 | 🟠 |
一直都有很多读者说，想让我用框架思维讲一讲基本的排序算法，我觉得确实得讲讲，毕竟学习任何东西都讲求一个融会贯通，只有对其本质进行比较深刻的理解，才能运用自如。
本文就先讲归并排序，给一套代码模板，然后讲讲它在算法问题中的应用。阅读本文前我希望你读过前文 手把手刷二叉树（纲领篇）。
我在讲二叉树的时候，提了一嘴归并排序，说归并排序就是二叉树的后序遍历，当时就有很多读者留言说醍醐灌顶。
知道为什么很多读者遇到递归相关的算法就觉得烧脑吗？因为还处在「看山是山，看水是水」的阶段。
就说归并排序吧，如果给你看代码，让你脑补一下归并排序的过程，你脑子里会出现什么场景？
这是一个数组排序算法，所以你脑补一个数组的 GIF，在那一个个交换元素？如果是这样的话，那格局就低了。
但如果你脑海中浮现出的是一棵二叉树，甚至浮现出二叉树后序遍历的场景，那格局就高了，大概率掌握了我经常强调的 框架思维，用这种抽象能力学习算法就省劲多了。
那么，归并排序明明就是一个数组算法，和二叉树有什么关系？接下来我就具体讲讲。