线性时间归并

归并排序剩下的部分就是 merge 函数，将两个相邻的以排序子数组， array[p..q] 和 array[q+1..r]，合并成一个在 array[p..r] 的有序子数组。我们将看到如何构造这个函数以使它尽可能高效。假设这两个已排序子数组总共有 $n$‍ 元素。为了将它们合在一起，我们要按顺序检查每一个元素，因此最理想的合并时间会是 $\mathrm{\Theta }(n)$‍。确实，我们将看到如何将 $n$‍ 元素用 $\mathrm{\Theta }(n)$‍ 的时间合并。

为了将已排序子数组 array[p..q] 和 array[q+1..r] 并在一起，而且让结果在 array[p..r] 中，我们首先要创造临时数组，并把 array[p..q] 和 array[q+1..r] 复制到这些临时数组中。我们在复制 array[p..q] 和 array[q+1..r] 中的元素之前不可以重写 array[p..r] 中的值。

因此，merge 函数的第一个任务是设定两个临时数组，lowHalf 与 highHalf，将 array[p..q] 中所有元素复制到 lowHalf 中，并将 array[q+1..r] 中所有元素复制到 highHalf 中。lowHalf 应该有多大？子数组 array[p..q] 具有 $q-p+1$‍ 个元素。那么 highHalf 呢？子数组 array[q+1..r] 具有 $r-q$‍ 个元素/（在 Javascript 中，我们创造数组时不用设定大小，但是因为很多其它的编程语言需要，我们介绍演算法时经常会考虑这一点）。

在我们的示例数组 [14, 7, 3, 12, 9, 11, 6, 2]，以下是我们递推排序 array[0..3] 和 array[4..7] （以使 $p=0$‍, $q=3$‍, 和 $r=7$‍），并将这些子数组复制到 lowHalf 和 highHalf 中，以后的样子：

array 中的数字变灰色是表示虽然这些数组的位置有值，“真正的” 值已经在lowHalf 和 highHalf中。我们可以任意重写灰色的数字。

接着，我们将这两个已排序，正在 lowHalf 与 highHalf 中的子数组并在 array[p..r] 中并在一起。我们应该将两个子数组之中最小的数值放进 array[p] 中。这个最小的数值会在哪里呢？因为子数组是排序的，最小的数值 一定 在两个位置当中之一： lowHalf[0] 或 highHalf[0]。（还有可能同一个值在两个位置都有，那么我们可以把其中任意一个叫做最小的值。） 只进行一此比较，我们就可以确定将 lowHalf[0] 或 highHalf[0] 复制到 array[p] 中。在我们的例子中， highHalf[0] 更小。让我们再建立三个变量来索引这些数组：

从 lowHalf 或 highHalf 复制到 array 中之后， 我们必须将 k 增值 (加 1) 来让我们将下一个最小的元素复制到 array 的下一个位置中。如果要从lowHalf 复制，要将 i 增值 , 如果要从 highHalf 复制，要将 j 增值。以下是读一个元素被复制回 array 前后的数组：

我们把 highHalf[0] 变灰色表示它已经没有我们要考虑的值。highHalf 数组中未被合并的部分在索引 j（现在是 1）开始。array[p] 中的值不再是灰色，因为我们将一个 “真的” 值复制进去了。

下一个要复制回 array 的值在哪里？它是在 lowHalf 中的第一个未被取用的元素 (lowHalf[0]) 或 highHalf 中的第一个未被取用的元素 (highHalf[1])。通过一次比较，我们确定 lowHalf[0] 更小，于是我们把它复制到 array[k] 中，并将 k 与 i 增值：

接下来，我们比较 lowHalf[1] 与 highHalf[1]，确定我们要将 highHalf[1] 复制到 array[k] 中。然后，我们将 k 与 j 增值：

继续下去，总是比较 lowHalf[i] 与 highHalf[j]，复制两者中较小的一个到 array[k] 中，并将 i 或 j 增值：

最终，lowHalf 或者 highHalf 中全部的值已被复制回 array 中。在这个例子中， highHalf 所有的元素在 lowHalf 的最后几个元素之前被复制。我们以复制 lowHalf 或 highHalf 当中未被取用的元素来完成：

我们声明过合并 $n$‍ 个元素要花 $\mathrm{\Theta }(n)$‍ 时间，因此合并在子数组大小的运行时间是线性的。让我们看看为什么这个说法成立。我们看到了合并有三个部分：

每个步骤需要执行多少行代码？每个元素 需要定量行代码。每个元素在第 1 步都从 array 复制到 lowHalf 或 highHalf 正好是一次。第 2 步中，每次比较花定量的时间，因为它只比较两个元素，每个元素最多只能 “赢” 一次比较。把第 2 步 和第 3 步合在一起，每个元素复制回 array 正好是一次。因为我们对于每个元素有定量次执行每行代码，假设子数组 array[p..q] 有 $n$‍ 个元素，合并的运行时间确实是 $\mathrm{\Theta }(n)$‍。

在下一个挑战中，你将实现这个线性运行时间的归并运算法。把这两个挑战合在一起，你就实现了完整的归并排序演算法。

本内容是 达特茅斯计算机科学 教授 Thomas Cormen 和 Devin Balkcom，与可汗学院的计算课程团队合作完成。内容获得许可 CC-BY-NC-SA。