トップダウンマージョソートでアレイが6NlogNにアクセスするのはなぜですか？

Question

長さNの配列をトップダウンマージソートで並べ替える理由は分かりませんが、6NlogNの配列アクセスだけが必要です。

各々は高々6Nアレイは、（コピーのため、2Nバック移動のため、最も2Nで比較のために2N）にアクセス

を使用してマージ（これは合計で6NlgNですので、各レベルは、高さがLGNであり、6N必要）

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に1。そして、ここに：

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

あなたはさらに別の2、この時間auxの読み取りとa上の書き込みを持っています。そして最後に、あなたが2以上を有していてもよく、ここで読み：

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

すべてのすべて：6の配列は、アクセス（4の読み取りと書き込みの2）。

上記のとおり、アルゴリズムはlogN深くなり、6NlogNになります。