首先要介绍函数，接着在图 3 - 28 中再次展示该函数。对于参数大小的合适量度 n 为待排序表的长度。在此，我们会用 T(n)来表示处理长度为 n 的表的运行时间。
我们选取 n 等于 1 的情况当作依据情况，而 n 大于 1（会发生递归调用）的情况则当作归纳情况。如果对其进行研究，就会知晓，除非是从另一个函数中调用参数为空表的情况，否则是无法在参数为空表的情况下进行调用的。原因在于，只有当表中至少有两个元素，也就是分拆后得到的两个表中都至少有一个元素时，才会执行第(4)行。因此可以忽略n=0的情况，并直接从n=1开始进行归纳证明。
LIST (LIST list)
LIST ;
如果 list 为 NULL ，则返回 NULL 。
如果 list 的下一个节点为 NULL ，那么就返回 list 。
else {
/* 表中至少有两个元素 */
(3) = split(list);
(4) merge((list), ());
复制代码
图 3-28归并排序算法
如果 list 仅由一个元素组成，那么就会执行第(1)行和第(2)行，其他代码则不会被执行。所以，在这种依据的情况下，T(1)属于 O(1)。
归纳。在归纳的情况里，第(1)行的测试失败了，同时第(2)行的测试也失败了。所以能够执行第(3)行和第(4)行的程序块。为了把问题简化，可以假定 n 是 2 的乘方。做出这种假定的好处在于，当 n 为偶数时，恰好能将表分割成两个长度均为 n/2 的等分。如果 n 是 2 的乘方，那么 n 除以 2 也是 2 的乘方。每次递归结束时，二分出来的都是等分的表。一直到每个表中只包含一个元素为止。当 n 大于 1 时，所花费的时间为下列各项的和。
直接看出接下来的情况并非易事。a 的系数与 n 的值是同步的，这意味着 T(n)等于 n 乘 a 再加上一定数量的 b。然而，b 的系数比 n 增长得更快。b 的系数与 n 的关系可归纳为：
n 的值24816
b 的系数
比率1234
比率由系数 b 除以 n 得到。所以，似乎 b 的系数是 n 乘上一个因子，这个因子在 n 每次翻倍时会增长 1。具体而言，我们能看出这个比率是 log2n，因为 log22 等于 1，log24 等于 2，log28 等于 3，且 等于 4。因此推测递推关系的解是 T(n)=an+bn log2n 是合理的，并且对于表示 2 的乘方的 n 而言是这样的。我们将会看到这个公式是正确的。
要求解该递推关系，需先依照前面示例中采用的策略。我们把归纳规则写成关于参数 m 的函数形式，形如
当 m 是 2 的乘方且 m 大于 1 时，T(m)等于 2 乘以 T(m 除以 2)再加上 bm(3.5)
经过这段分析之后，需要把常数 a 和 b 替换为大 O 表达式。也就是说，T(n)是 O(n)加上 O(n logn)。因为 n 比 n logn 增长得更慢，所以能够忽略 O(n)这一项，直接表明 T(n)是 O(n logn)。这也就意味着，归并排序算法的时间量级为 O(n logn)。请记住，我们已经证实了选择排序的运行时间为 O(n2)。尽管严格来说，这里的 O(n2)仅仅是一个上界，但实际上它是选择排序的最紧简单边界。所以，可以明确，随着 n 持续变大，归并排序始终会比选择排序运行得更快。从实际情况来看，对于值大于几十的 n 而言，归并排序比选择排序更快。
请记住，在大 O 表达式里，我们无需为对数去指定底数。因为这里的对数处于常数因子之中，所以所有底数的对数都是相同的。
