Why does mergesort have at most 6 n log n array accesses?

Question

I'm watching the Coursera Princeton algorithms lecture on merge sort and I understand all of the analysis except for a merge being at most 6 n log n array accesses.

Why 6?

Answer 1

To get 6 array accesses, a somewhat inefficient merge process:

read  - read an element from even run for compare
read  - read an element from odd  run for compare
      - compare
read  - read the lower element again for copy
write - write the lower element to the output array for copy
...   - after merge copy back
read  - read element from output array to copy back
write - write element back to original array to copy back

The normal case is one read and one write for every element moved, but consider the case where elements are too large to fit in a variable, like a string, so after a compare, the string to be moved has to be read again.

Usually the copy back operation can be avoided, depending on how the merge sort is coded.