algorithm - 为什么合并排序最多有 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

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

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