归并排序 怎么工作

一格一格太慢

上次的方法好在简单：比较相邻的两个，把大的往后送就行。
可是队伍一长，要比较的就太多了。
卡片翻一倍，比较次数就涨到四倍。四张很快，三十二张就遥遥无期了。

把队伍翻一倍试试。长度翻倍 → 比较次数涨到四倍。

柱子吓人地往上蹿。
队伍越长，慢得越厉害。
问题出在把整支队伍当成一整块，从头比到尾。
那么，把这一整块拆开会怎样？

一分为二

不要把长队伍整个拿来处理，而是一分为二。
把这一半再分成两半，再分，再分，最后就只剩下一格一格的。
而一格本身就算排好了，因为只有一个，没有可比的。

把一组不断地一分为二。8 → 4+4 → 2+2+2+2 → 一格一格。

光拆开就完了吗？
没有。拆开的还得重新合起来才成队伍：把单格两两配对合并，再把合好的继续合并。
而把两组排好的合并，其实意外地简单。

合并两组排好的

把两组排好的合成一队，诀窍是只看最前面。
比较两组的第一格，把小的那个放进结果里。那个位置由下一格补上，再比较两组的第一格。
就像拉拉链一样，一格一格地咬合起来。

比较两组最前面的，把小的放下去。像拉链一样一格一格合并。

是不是很神奇？比较整个乱糟糟的队伍时很慢，可合并两组各自排好的，只看最前面就行，所以很快。
拆开以后有了排好的小块，再把这些小块一层层合起来，不知不觉就成了完整的队伍。

为什么快：层数

为什么这样更快？
因为是一分为二，拆的层数并不多。队伍翻一倍，层数只多一层。
合并一层的代价大约是队伍长度，所以总代价就是层数乘以队伍长度。
这比一格一格比较（长度乘长度）增长得慢得多。

展开各层，改变队伍长度试试。层数 x 一层 = 比一格一格增长得慢。

准确的公式以后再学。
现在只要带走一个感觉：一分为二，层数增长得慢，每一层又合并得轻松，所以整体就快了。
拆开再合并，这一招就让速度大大改观。

总结

串成一条线，就是这样。
一格一格比较的排序，队伍越长越慢。
所以把队伍一分为二，一直拆到单格，单格就是已经排好的小块。
把排好的两组像拉链一样合并，只要合并层数那么多次，整支队伍就能快得多地排好。
拆开再合并，这就是聪明排序的核心。

依次点这四步，跟着走一圈。拆开 → 单格 → 合并 → 只合并层数那么多次 = 快。

这里我们总是从中间平平稳稳地一分为二。
不过还有个“表亲”，选分界点的方法稍有不同：不选中间，而是选某一格作为基准，把其余的分成比它小和比它大的两部分。
这个基准怎么选，就留到以后再讲。
今天只要记住：一分为二再合并，就会变快。