为什么数组在自上而下的合并排序中访问 6NlogN？

Question

不太明白为什么要对长度为N的数组进行自上而下的归并排序，只需要访问6NlogN次数组。（每一层需要6N，高度是lgN，所以一共是6NlgN）

每次合并最多使用 6N 次数组访问（2N 次用于复制，2N 次用于移回，最多 2N 次用于比较）

不是把N个元素复制到辅助数组中，再复制回原来的数组，也就是2N个吗？ 2N "move back" 来自什么？

这道题其实出自《算法归并排序》中的Progosition G。我想为此。

就是下面书中的代码：

public static void merge(Comparable[] a, int lo, int mid, int hi) 
{  // Merge a[lo..mid] with a[mid+1..hi].
   int i = lo, j = mid+1;
   for (int k = lo; k <= hi; k++)  // Copy a[lo..hi] to aux[lo..hi].
      aux[k] = a[k];
   for (int k = lo; k <= hi; k++)  // Merge back to a[lo..hi].
      if      (i > mid)              a[k] = aux[j++];
      else if (j > hi )              a[k] = aux[i++];
      else if (less(aux[j], aux[i])) a[k] = aux[j++];
      else                           a[k] = aux[i++]; 
}

public class Merge 
{  
   private static Comparable[] aux;      // auxiliary array for merges
   public static void sort(Comparable[] a)
   {
      aux = new Comparable[a.length];    // Allocate space just once.
      sort(a, 0, a.length - 1);
   }
   private static void sort(Comparable[] a, int lo, int hi)
   {  // Sort a[lo..hi].
      if (hi <= lo) return;
      int mid = lo + (hi - lo)/2;
      sort(a, lo, mid);       // Sort left half.
      sort(a, mid+1, hi);     // Sort right half.
      merge(a, lo, mid, hi);  // Merge results (code on page 271).
   } 
}

Answer 1

我看到的是您只调用了读取操作 "array accesses"，而书中将读取和写入操作都称为 "array accesses"。查看 merge 代码。您在这里有 2 个数组访问：

aux[k] = a[k];

对 a 的读取操作和对 aux 的写入操作。那么这里：

a[k] = aux[j++]; //or aux[i++];

您还有另外两个，这次是 aux 上的读取和 a 上的写入。最后，你可能还有两个阅读这里：

less(aux[j], aux[i])

总计：6 次数组访问（4 次读取和 2 次写入）。

正如您所提到的，算法深度为 logN，因此我们得到 6NlogN。

为什么数组在自上而下的合并排序中访问 6NlogN？

Why is the array access 6NlogN in a Top-down mergesort?

arrays

algorithm

merge

mergesort

array-merge