Warum greift das Array in einem Top-Down-Mergesort auf 6NlogN zu?

Question

Ich verstehe nicht ganz, warum ein Array der Länge N durch eine Top-Down-Merge-Sortierung zu sortieren, es benötigt nur 6NlogN Array-Zugriffe. (Jede Stufe erfordert 6N, die Höhe ist LGN, so ist es 6NlgN insgesamt)

Jede merge verwendet höchstens 6 N-Array zugreift (2N für die Kopie, 2N für die Bewegung zurück und höchstens 2N vergleicht for)

Kopiert es N Elemente nicht in Hilfs-Array und kopiert es zurück in das ursprüngliche Array, das ist 2N? Woher kommt die 2N zurück?

Die Frage ist eigentlich von Proposition G in Mergesort von Algorithmen. Ich denke dafür.

Es ist der Code in dem Buch unter:

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

Was kann ich sehen, ist, dass Sie nur die Leseoperationen als „Array zugreift“, während das Buch sowohl für den Lese- bezieht und die Schreiboperationen als „Array Zugriffe ". Schauen Sie sich den Code merge an. Sie haben 2-Array hier greift:

aux[k] = a[k]; 

Ein Lesevorgang auf a und ein Schreib eine auf aux. Dann hier:

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

Sie haben noch zwei weitere, diesmal einen Read auf aux und eine Schreib auf a. Und schließlich kann man zwei weitere liest hier:

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

Alles in allem: 6 Array-Zugriffe (4 liest und schreibt 2).

Wie Sie erwähnt haben, geht der Algorithmus logN tief und so erhalten wir 6NlogN.