为什么归并排序最多有 6 n log n 数组访问？

Question

我正在观看 Coursera 普林斯顿算法关于合并排序的讲座，我理解所有分析，除了最多 6 n log n 数组访问的合并。

为什么是6？

Answer 1

要获得 6 次数组访问，这是一个效率较低的合并过程：

read  - read an element from even run for compare
read  - read an element from odd  run for compare
      - compare
read  - read the lower element again for copy
write - write the lower element to the output array for copy
...   - after merge copy back
read  - read element from output array to copy back
write - write element back to original array to copy back

正常情况是每个移动的元素进行一次读取和一次写入，但考虑到元素太大而无法放入变量（例如字符串）的情况，因此在比较后，必须再次读取要移动的字符串。

通常可以避免复制回操作，具体取决于合并排序的编码方式。

Answer 2

我也想知道 6。我观看了 Tim Roughgarden 的分析（视频“1 - 7 - 合并排序 - 分析（9 分钟）.mp4”），他也说是 6。每个解释都感觉像是在挥手，但也许因为它太简单了，他们没有意识到需要解释：

当复制到辅助数组时，每个 n（或 k）访问一个数组两次

aux[k] = a[k];

然后，在最坏的情况下，您永远不会耗尽子数组（您只比较常量），这样您就有四个以上的数组访问

else if (less(aux[j], aux[i])) a[k] = aux[j++];

（例如，如果输入顺序相反）或每个比较失败，而 else 在比较后启动（正确的顺序），或两者的某种组合。这并不重要，只是根据最坏情况的定义，您无法通过常量（使用

if (i > mid)

或

else (j > hi)

）转义数组访问，因此每个 k 这里还有四个。总共是 6 个。

（每一行代码都是 Sedgewick 的 - 他的文本第 p271 页。）

Answer 3

考虑一个大小为 N 的数组“a”。为了应用归并排序，我们引入另一个与“a”大小相同的数组“aux”。讲座中所讲的mergeSort的相关代码是：

private static void sort(Comparable[] a, Comparable[] aux, int lo, int hi){
if(hi<=lo) return;
int mid = lo + (hi-lo)/2;
sort(a,aux,lo,mid);/*Line1*/
sort(a,aux,mid+1,hi);/*Line2*/
merge(a,aux,lo,mid,hi);/*Line3*/
}
public static void sort(Comparable[] a){
aux = new Comparable[a.length];
sort(a,aux,0,a.length-1);
}

现在，只考虑mergeSort的合并部分，这意味着Line1和Line2已经完成了它们的工作，也就是说，我们现在将'a'分为两半，每一半都已排序。 我们将一半称为 s_l（对于子数组“左”），将另一半称为 s_r（对于子数组“右”）。 第 3 行给出了合并这两个子数组的调用。为此，我们将所有这些元素复制到“aux”中，该文件到目前为止还是空的。这需要对“a”进行“N”次数组访问，对“aux”进行“N”次数组访问，总共需要“2N”次。此外，在合并过程中，我们将元素从“aux”复制回“a”（如下面第 4、5、6 和 7 行所示），这需要另外 2N 次数组访问。 现在有趣的部分来了。合并的代码是：

int i = lo, j = mid+1;
for (int k = lo; k <= hi; k++) 
 {
 if (i > mid) a[k] = aux[j++];/*Line4*/
 else if (j > hi) a[k] = aux[i++];/*Line5*/
 else if (less(aux[j], aux[i])) a[k] = aux[j++];/*Line6*/
 else a[k] = aux[i++];/*Line7*/
 }

您似乎很清楚最多可以有“N”个。合并时发生的比较。那么很容易理解，对于每次比较，我们需要 2 次数组访问，这意味着我们最多需要 '2N' 次数组访问来比较元素。因此，归并排序的合并部分总共需要最多 6N 次数组访问。应用递归公式：

A（N）<= A(N/2) + A(N/2) + 6N,

其中 A(N) 是编号。排序数组 'a' 的访问次数，A(N/2) 表示次数。用于排序 s_l 和 s_r 的数组访问次数（在 Line1 和 Line2 中），6N 表示合并 s_l 和 s_r 所需的额外数组访问次数。 解决这个递归给出了最大的数。数组访问次数等于 6NlgN。

最好的， 谢克鲁。

PS： 对于那些不清楚粗体和斜体部分的人：

由于有 N 个元素，所以应该清楚不会有超过 N 次比较（因为对于放回 'a' 的每个元素，最多可以发生一次比较）现在出现的问题是何时相等坚持住？

考虑如下情况：

s_l = [1,3,5,7,9]

s_r = [2,4,6,8,10]

当我们在上面应用合并函数时，我们看到我们必须访问数组 2N = 20 次，这是最大限制。这意味着最大数量。当 s_l 和 s_r 的情况下需要进行数组访问

s_l[i]