归并排序（ merge sort ）是一种采用 分治法（ divide and conquer ）设计的高效排序算法，时间复杂度为 $O(n\log{n})$ 。它的设计思路很直白，主要分为三步：
- 问题划分：将待排序序列平均划分为两个部分；
- 子问题求解：分别对两个子序列进行排序（递归执行归并排序）；
- 结果合并：将两个已经排好顺序的子序列合并成一个完整的有序序列，得到最终结果；
分治法 是计算机科学中一种很重要的算法设计思想，简单概括就是“分而治之”：将一个复杂的问题，分解成两个或多个子问题，再对子问题进行求解，最终合并成原问题的解。
随着问题的划分，子问题规模逐渐变小，求解难度逐渐降低，最终达到可以直接求解的程度。
合并有序序列
归并排序最为关键的一步是最后的 结果合并 ，即：将两个已经排好顺序的子序列合并成一个完整的有序序列。那么，有序序列应该怎么合并呢？
思路其实很简单。先准备一个临时存储空间，用来保存合并后的完整序列，可称为目标序列。合并时只需不断地从两个子序列中取出最小元素，然后依次写入目标序列即可。
由于子序列已经排好顺序，它们各自的最小元素均位于序列 头部 。因此，我们只需比较子序列头部元素的大小，即可找到它们的最小值。具体步骤如下：
- 变量 $i$ 用于记录目标序列下一个待合入元素，指向临时存储空间下一个待写入位置；
- 变量 $j$ 、$k$ 用于遍历两个子序列，开始时分别指向子序列①和②的头部；
- 循环比较两个子序列中，$j$ 、$k$ 指向的头部元素大小，并视情况处理：
- 如果 $j$ 指向的序列①头部元素不大于序列②，将它写入 $i$ 指向的位置，并分别自增 $i$ 、$j$ ，使其分别指向下一个位置；
- 否则意味着 $k$ 指向的序列②头部元素更小，将它写入 $i$ 指向的位置，并分别自增 $i$ 、$k$ ，使其分别指向下一个位置；
- 如果两个子序列中有一个已经合并完毕，则将另一个的剩余部分依次拷贝到目标序列即可；
下面这个动画，很好地演示了合并有序序列的整个过程：
合并有序序列示例代码如下，可结合注释和动画对照理解：
归并排序
掌握了合并有序序列的方法，理解归并排序也就毫无难度了：
- 先检查待排序序列的长度，如果元素个数少于 2 ，则无需处理；
- 将待排序序列平均划分为两部分（问题划分）；
- 递归 执行归并排序算法分别对两个子序列进行排序（子问题求解）；
- 将两个已经排好序的子序列合并起来，并保存到辅助存储空间（结果合并）；
- 将结果从临时存储空间中，拷贝回原序列；
递归算法需要特别注意 退出条件 。在归并排序算法中，随着序列的层层划分，长度不断减半。当长度最终降到 2 以下时，递归调用便结束。
这个动画很好的演示了归并排序的过程，可以帮助理解：
归并排序示例代码如下，可结合注释和动画对照理解：
递归细节
如果觉得归并排序递归调用很难理解，可以观察下面这个动画，来获得启发。动画右边的树形结构，形象地描述了序列层层分解的过程。红框则标注了当前的执行进度，为你揭开递归调用的神秘面纱：
完整代码
【小菜学算法】系列文章首发于公众号【小菜学编程】，敬请关注：
小菜学编程
