algorithm - 优化合并排序

Question

归并排序是一种相当常见的排序算法，我已经编写了一个有效的归并排序算法。然后我想优化它。第一步是将它从递归转换为迭代，我做到了。然后我无法辨别还有什么可以优化的。在网上查阅了很多文章后，我得到了两种机制，使用multi-merge 排序和tiled merge-sort。然而，这些文件都没有提供任何伪代码，甚至都没有详细解释如何做到这一点，以及它如何提供其作者所说的优势，比如缓存友好和改进的局部命中率。

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

Answer 1

您可以进行的一种常见且相对直接的优化是，当子数组大小低于某个阈值时，从合并排序切换到另一种算法，如插入排序。尽管归并排序的运行时间为 O(n log n)，但这只是在谈论它的长期增长率，并没有说明该算法在小输入上的表现如何。例如，插入排序在小输入规模上运行得非常快，尽管从长远来看它会更糟。因此，考虑更改合并排序的基本情况，以便如果要排序的数组低于某个大小阈值(例如 50-100)，则使用插入排序而不是继续递归。从经验来看，这可以显着提高算法的性能。