为什么自上而下的Mergesort中的数组访问6nlogn

Question

我不太了解为什么通过自上而下的合并排序对长度n进行排序，它只需要6nlogn数组访问。（每个级别都需要6n，高度为lgn，因此总计为6NLGN）

每个合并最多使用6N数组访问（副本为2N，2N的移动2N，最多2N用于比较）

）

它不是将n元素复制到辅助数组中，然后将其复制回原始数组，哪个是2n？什么是2n"向后移动"？

这个问题实际上来自算法正交中的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访问"。查看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个写入）。

您提到的，该算法深入登录，因此我们获得了6nlogn。