arrays - 什么更贵 : compare or accessing an index of array

Question

基本上我在 youtube 上看到了可视化排序算法的视频，他们提供了程序以便我们可以使用它.. 程序计算两个主要的东西(比较，数组访问).. 我想看看哪一个(合并和快速)排序是最快的..

100个随机数

快速排序:
比较 1000
数组访问 1400

合并排序:
比较 540
数组访问 1900

所以快速排序使用较少的数组访问，而合并排序使用较少的比较，并且差异随着索引数量的增加而增加..那么计算机更难做哪一个？

Answer 1

数字不对。实际运行 100 个随机数的结果。请注意，快速排序比较计数受实现的影响，Hoare 使用的比较比 Lomuto 少。

快速排序(霍尔分区方案)

pivot reads      87   (average)
compares        401   (average)
array accesses  854   (average)

合并排序:

compares        307  (average)
array accesses 1400  (best, average, worst)

由于数字正在排序，我假设它们适合寄存器，这减少了数组访问。

对于快速排序，比较是针对一个枢轴值进行的，每个递归的快速排序实例应该只读取一次枢轴值并将其放在寄存器中，然后为每个比较的值读取一次。优化编译器可能会将用于比较的值保留在寄存器中，以便交换已经在寄存器中具有两个值并且只需要进行两次写入。

对于合并排序，比较对数组访问几乎增加了零开销，因为比较的值将被读入寄存器，进行比较，然后从寄存器中写入，而不是再次从内存中读取。