爲什麼數組在一個自頂向下的mergesort中訪問6NlogN？

Question

我不太明白爲什麼要用自頂向下的合併排序對長度爲N的數組進行排序，它只需要6NlogN數組訪問。 （每級需要6N，高度爲LGN，所以它的6NlgN總共）

每個合併使用至多6N數組訪問（2N用於複製，2N爲回遷，並且至多2N用於比較）

是不是將N個元素複製到輔助數組中並將其複製回原始數組，即2N？什麼是2N「退回」？

這個問題實際上來自算法Mergesort中的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

我能看到的是，只調用讀操作「數組訪問」，而這本書既指讀，是「陣列寫操作訪問」。 查看merge的代碼。你有2個數組訪問這裏：

aux[k] = a[k]; 

A於a讀操作和aux寫一個。那麼在這裏：

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

您還沒有另外兩個，此時就aux讀取和a寫。最後，您可能在這裏有兩個更多的讀取：

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

總而言之：6個數組訪問（4次讀取和2次寫入）。

正如你所提到的，該算法進行logN深入，所以我們得到6NlogN。