为什么归并排序最多有 6 n log n 数组访问？

Question

我正在观看 Coursera 普林斯顿算法关于合并排序的讲座，我理解所有分析，除了最​​多 6 n log n 数组访问的合并。

为什么是 6？

Answer 1

要获得 6 次数组访问，这是一个效率较低的合并过程：

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

正常情况是每个移动的元素进行一次读取和一次写入，但考虑到元素太大而无法放入变量（例如字符串）的情况，因此在比较之后，必须再次读取要移动的字符串。

通常可以避免复制回操作，具体取决于合并排序的编码方式。