每周学点大数据 | No.22 外排序
No.22期
外排序（一）
Mr. 王：接下来我们看一看在磁盘算法中一个比较典型的例子——外排序。
小可：那什么又是外排序呢？
Mr. 王：外排序是相对内排序而言的，当要排序的数据量无法被全部装进内存时，我们就需要用到外排序，此时有大量的数据被存在硬盘里，无法直接进行操作，必须先以块为单位读进内存中。
为了更好地理解大数据中的归并排序，我们先从内存中的归并排序说起。该算法被称为“归并排序”或者“多路归并排序”，其基本思想就是，先将整个数组划分为多组，保证每一组内是有序的，然后相邻的两组之间进行“归并”，使得产生的更大的组也是有序的，直到组的大小等于数组的大小。
归并排序体现了一个重要的算法思想——分治法。分治法是设计很多算法时一种有效的策略。
对于一个比较大、复杂的问题，我们很难一下子将其解决，这时就尝试采用将大的问题逐渐划分为小的问题，这些小的问题叫作子问题，对于子问题，求解起来往往会变得容易一些。
当然，我们还可以对子问题进行进一步的划分，划分成更小的子问题，在很多问题中，当子问题被划分得足够小时，就可以使用很简单的方法解决或者直接得到解决了。当这些子问题有效地得到解决时，我们就可以按照子问题和原问题的关系逐步将子问题的解进行合并，从而得到原来问题的解。
小可：这也符合我们日常生活中处理问题的思路。对于一个比较棘手的问题，我们会尝试将其分成多个较小的部分，再逐个击破，最后把各部分的解决方案拼到一起，就得到了原来那个大问题的解。
Mr. 王：归并排序其实就是分治法的一种典型体现，在二路归并排序中，首先要将整个乱序的序列划分为两路，然后分别对两路进行一个归并排序。注意，这个过程会递归地进行下去。也就是说，对划分出来的两路继续执行划分，变成四个部分，再从四个部分进行划分，变成八个部分，依此类推。
最后直到整个分成了只含有一个元素的序列时，它显然就已经排好序了，我们再把这些排好序的序列进行逐级合并，合并成长度为2,4,8,16 的序列。
小可：其实划分这个步骤非常容易做，关键就在于合并这个步骤怎么解决，怎么把两路已经排好序的序列合并到一起，成为一个仍然有序的序列呢？
Mr. 王拿出两组扑克牌放在桌面上，说：想一想，假设我们有两个有序的数字卡牌序列，分别是2468 和1357，我们要如何将其变成一组有序的数列，即12345678 呢？
在归并排序的合并中，我们可以用两个硬币来模拟移动的指针。首先，我们把两个指针分别放在两个序列的第一张牌上，由于两路都是有序的，所以这两张牌一定都是两路中最小的。
但这两张牌也是有大小关系的，不难想到，这两张牌里面最小的一定是所有8 张牌里面最小的。根据排序的问题定义，按照从小到大的顺序排列，所以第一次我们希望能够找出序列中最小的那个数。
于是，我们比较两个硬币所在的扑克牌，发现1 比2 小，所以取出1，放在外面，然后将硬币向右移动一个位置，放在3 上面。现在我们要找出8 张牌中第二小的。
小可：从8 张牌中拿出了最小的，那么剩下的7 张牌中最小的就是第二小的，所以我们只要找到剩下的7 张牌中最小的就可以了。方法还是和前面的一样，因为现在的两个硬币依然在两组数中最小的两个数上，只要比较它们的大小就可以了。一个是2，一个是3，所以取出2。
Mr. 王：很好，但别忘了将硬币再向右移动一个位置，此时在3 和4 上面。我们取出3，再将硬币向右移动。不断地进行这个步骤，最后就会发现，我们取出扑克牌的顺序刚好就是12345678。这样就非常有效地将两个大小为4 的序列合成一个大小为8 的序列，而同时满足了这个大小为8 的序列仍然有序这一要求。
小可：那从1 到2，2 到4，4 到8，8 到16 都可以用这个方法进行操作实现，所以对于任意的序列长度n，我们都可以用这个方法进行排序了。嗯，内存中的归并排序方法我基本上搞懂了。
Mr. 王：别急，我们先来看看这个算法的时间复杂度如何。
小可：这个可有点复杂，要怎么分析呢？
Mr. 王：其实要求解这类问题的时间复杂度，需要用到算法设计分析理论中的一个重要定理，叫作Master 定理，这是一个可以求解递归式的复杂度的定理。不过，今天我们尝试用一种比较直观的方法进行分析。首先看一下这个图：
在最后一轮中，将两个长度为n/2 的序列进行了归并，合并成长度为n 的序列。每个元素被访问了几次？
小可：根据我们前面说过的合并方法，每个元素实际上都被访问了常数次，因为就是做了一个简单的比较，所以应该是cn 次。
Mr. 王：那么倒数第二轮呢？
小可：在倒数第二轮中，有4 个序列被合并成2 个，其中一个合并过程有n/2 个元素参与，所以应该是cn/2，这样的过程应该有两个，所以依然是cn 次。
Mr. 王：由此发现，不管有多少个序列参与归并，其实在每一轮的归并中，都是访问了所有的元素常数次，每一轮都进行了cn 次的操作。这意味着归并排序中每一轮的复杂度都是O(n)。
小可：这个我懂了，只要知道整个归并排序进行了多少轮，再乘以O(n) 就可以了。
Mr. 王：很好，思路是非常正确的。现在我们来观察一下合并这个过程。
Mr. 王指着那个模拟合并过程的图，说道：如果将这里的每一个序列都看作一个节点，将图中的箭头线看作边，那么这是一个什么特殊的图？
小可恍然大悟，说：这是一棵树！！
Mr. 王：不难看出，树的每两层之间的边，就代表了进行一次归并。也就是说，树的高度-1就是进行归并的次数。
小可：没错，所以我们只要知道树的高度是多少就行了！
Mr. 王：好，这是一棵满二叉树，它有n 个叶子节点，这课树的高度是多少呢？
小可：满二叉树的内部节点数量为叶子节点数量-1，所以这棵树有2n-1 个节点；而一棵有N 个节点的树的高度是h=O(logN)，所以就是h=O(logn)。
Mr. 王：综合起来，归并排序的时间复杂度就是O(logn)·O(n)=O(nlogn)。前面我们提过，基于比较的排序算法，它的时间复杂度下界是O(nlogn)。这说明它已经是一个非常高效的算法了。
归并排序的好处不仅仅是它的效率高，更重要的是它能够非常有效地应用在外排序中。在现实生活中，需要排序的数据量有时候是很大的，当内存中无法容纳这么大的数据量时，我们就要尝试将这些数据存储在磁盘上，利用内存作为数据的暂存地进行排序。
小可：那么在外排序中，归并排序又该怎么做呢？
Mr. 王：此时我们就要思考如何充分地利用内存空间了。将整个数组分为多少路，要考虑内存能装下多少个磁盘块，我们要分的路数等于内存能装下的磁盘块数。也就是说，一定要保证每一路都有一块在内存中。
内容来源：灯塔大数据