先说个常见的面试题，对非常多的数据进行排序，例如对5亿个数进行排序，但是内存中只能容纳5千万的数据，这时候就要用到外部排序，多路归并排序。这里不做详细介绍，只说下大概的流程：
（1）对数据进行分片，因为内存容纳5千万，那么把数据分为10段。
（2）每一段依此放入内存进行排序，在写回硬盘。
（3）取每一段的头，取最小值，写入最终文件，然后补充数据。
下图，取每一段的第一个元素，因为每一段数据都是有序的，所以第一个元素是在每一段中的最小的。
然后在这些树中取最小值，那么就是全局的最小值。把最小值写入最终文件中。可以看到取到的最小值是2。
2被取出来后，用第2段数据的第一个继续补充，然后重复这个过程。
怎么能够高效的获取最小值呢？直接遍历数组可以，但是这个时间复杂度是O(n)的，显然不可行。那么这里就用到了败者树。
想要了解败者树，那么就先构造一个败者树，下面是构造的过程：
假设要重下面这些数据中获取最小值：
（1）按照数组下标进行编号。构造出6棵树，树的根是数组的下标，叶子节点是值。
（2）随便取两棵树进行合并，例如，第1个和第2个合并，第4个和第5个合并。合并的规则是，比较两个数的值，较小值的下标作为合并后树的根节点，较大的作为根的子节点。拿前两个合并为例，6小于18，那把6对应的下标（1）作为根，18对应的下标（0）为根的子节点（也是叶子节点的父节点）。
可以看出来，合并的过程就是两棵树进行比较的过程，把小的（败者）放在最上面，这样是“败者树”的名称的由来。这样一直合并上去，那么最上面的肯定是全局最小的。
（3）继续合并，第1和第2棵树。看根节点对应的值，数组中编号为1的值是6，编号为2的是12，比较，6小于12所以根是1.
(4)继续合并。整个败者树生成，根节点就是最小的节点，根节点是1，编号为1的值是6，可以看出6确实是数组中的最小值。
（5）按照前面说的多路归并的过程，取出最小值6。然后补充数据进来。新补充的数据是33，可以看出已经不符合败者树的规则了，重新构建。
（6）把不符合规则的拆出来。
（7）把树归位，编号0对应18，编号1对应33.
（8）重新按照规则进行合并。
（9）这时候2节点的左节点没有，那么把2拆出来。
（10）合并。
（11）继续合并。新的败者树完成，新的最小值是2，这次的比较次数只有3次，因此败者树的效率是很高的。
（12）继续取出最小值。
这样就可以完成整体的排序了。
