优化Mergesort

Question

合并排序是一种相当常见的排序算法，我写了一个工作的合并排序算法。然后我想优化它。第一步是将其从递归转换为迭代，我就是这样做的。然后我看不出还有什么可以优化的。经过网络上的大量文章，我得到了两个机制，使用多合并排序和平铺合并排序。然而，没有任何文件提供任何伪代码，甚至不关心如何去做，以及它如何提供其作者所说的优点，如缓存友好和改进的局部性。

任何人都可以详细说明这个问题，如果可能的话，提供一些伪代码？具体来说，我想知道如何让它缓存友好。我完全不知道这些东西是什么，否则我会自己尝试。

Answer 1

您可以进行的一种常见且相对直接的优化方式是，当子阵列大小低于某个阈值时，从mergesort切换到另一种算法，如插入排序。虽然mergesort运行时间为O（n log n），但它谈到了它的长期增长率，并没有说明算法在小输入上表现如何。例如，插入排序在小输入尺寸下运行速度非常快，即使长期运行情况更糟糕。因此，考虑更改mergesort的基本大小写，以便如果要排序的数组低于某个大小阈值（例如50-100），则使用插入排序而不是继续递归。从经验来看，这可以显着提高算法的性能。