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

Question

I don't quite understand why to sort an array of length N by a top-down merge sort, it only needs 6NlogN array accesses. (each level requires 6N, the height is lgN, so it's 6NlgN in total)

Each merge uses at most 6N array accesses (2N for the copy, 2N for the move back, and at most 2N for compares)

Doesn't it copy N elements into auxiliary array and copy it back to original array, which is 2N? What is the 2N "move back" from?

The question actually is from Progosition G in Mergesort of Algorithms. I think for this.

It's the code in the book below:

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

What I can see is that you call only the read operations "array accesses" whereas the book refers both to the read and the write operations as "array accesses". Look at the merge code. You have 2 array accesses here:

aux[k] = a[k];

A read operation on a and a write one on aux. Then here:

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

You have yet another two, this time a read on aux and a write on a. And at last, you may have two more reads here:

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

All in all: 6 array accesses (4 reads and 2 writes).

As you mentioned, the algorithm goes logN deep and so we get 6NlogN.