13.4　合并排序

选择排序算法很简单，但效率不高。要想对 n 个元素进行排序，它必须遍历数组 n-1 次。每次遍历所需要的时间与 n 成正比，因此总时间与 n² 成正比。

在接下来的两节中，我们将实现一种效率更高的算法——合并排序（merge sort）。对 n 个元素进行排序时，合并排序所需的时间与 n log₂n 成正比。这看似没什么大不了，但当 n 很大时，n² 和 n log₂n 的差别将非常大。

例如，log₂1000000 的值大约为 20。因此，如果要对 100 万个数字进行排序，选择排序需要 1 万亿步，而合并排序只需 2000 万步。

合并排序的理念如下：如果有两堆已排好序的牌，将它们合并成排好序的一堆牌将既容易又快捷。请用一整副牌来尝试这种算法。

(1) 将整副牌分成两堆，每堆大约 26 张；分别对每堆牌进行排序，使其面朝上时最小的牌位于最上面；将两堆牌都面朝上放在你面前。

(2) 比较两堆牌最上面的那张，选择较小的，将其翻过来并加入合并堆。

(3) 重复第 2 步，直到其中一堆没牌，再将另一堆中余下的牌全都翻过来并加入合并堆。

结果是排好序的整副牌。接下来的几节将介绍如何用 Java 实现这种算法。