更聪明地排成一列

一格一格地慢

上回的法子简单，挺好。
挨着比，大的往后。
可队一长，
要比的事就太多了。
卡片翻一倍，
比较就跳到四倍。
四张很快，
三十二张就遥遥无期了。

试着把队翻一倍。(长度翻倍 → 比较跳到四倍)

柱子涨得吓人吧。
队越长，
慢得越厉害。
问题就出在：
把整条队当成一坨，
一直比到头。
那要是把这坨
拆开呢?

对半分开

别整条长队一起弄，
对半分开。
那一半再对半，
那一半也再对半。
一直分下去，
最后只剩单个。
可单个
本身就已排好。
就一个，没什么可比的。

把一束不停对半分。(8 → 4+4 → 2+2+2+2 → 单个)

分开就完事了吗?
不，分开的块
得重新合到一起才成队。
把单个
两两配对合并，
合好的再合。
而合并排好的两块，
出乎意料地容易。
下面就看。

合并排好的两个

有两个排好的束。
要把它们合成一列，
窍门是只看最前面。
比两束的第一格，
把较小的落进结果。
那个位子由下一格补上，
再比最前面。
像拉链合上一样，
一格一格咬合着合到一起。

比两束的最前面，落下较小的。(像拉链一样一格一格合并)

是不是很妙?
比一整坨乱的时候慢，
可合并两个各自排好的，
只看最前面，就快了。
多亏拆开，
有了小小的、排好的碎块，
把这些碎块一点点合上去，
不知不觉就成了一整列。

为什么快: 层的数量

为什么这个更快?
因为对半分，
分的层数没几层。
队翻一倍，
层只多一个。
而合并一层的花费，
约等于队长。
所以总花费是
层数乘以队长。
比一格一格(长度乘长度)
增长得慢得多。

展开层、改变队长。(层数 x 每层 = 比一格一格涨得慢)

精确的公式以后再学。
现在只把感觉带走。
对半分，
层增长得慢吞吞，
每层又轻轻松松地合，
所以整体就快了。
分开再合并这一招，
把速度一下子改写了。

来小结一下

串成一条线，是这样的。
一格一格比的排序，
队越长越慢。
所以把队对半分，
一直分到单个，
也就是已经排好的碎块。
把这些排好的像拉链一样合并，
只要合并层数那么多次，
整条队就快得多地齐了。
分开再合并。
这就是聪明排序的核心。

依次点四个步骤，跟着走一圈。(分开 → 单个 → 合并 → 只算层数 = 快)

这里的合并，总是稳稳地对半分。
不过还有个表亲，
分的标准有点不一样。
不是取中间，
而是拿某一格当记号，
分成较小的和较大的两堆。
那个记号怎么挑，
留到以后再讲。
今天只把这个带走:
对半分开再合并，就快了。