优化Mergesort

Question

合并排序是一种相当常见的排序算法，我已经编写了一种有效的合并排序算法.然后我想优化它。第一步是将它从递归转换为迭代，我就是这样做的。然后我看不出还有什么是可以优化的。在网上浏览了大量文章后，我得到了两种机制，一种是使用多重合并，另一种是使用平铺合并排序。然而，这些文档中没有一个提供了任何伪代码，甚至都不愿意解释如何做到这一点，以及它如何提供作者所说的优势，比如对缓存友好和本地性的改进。

有人能详细说明这件事吗?如果可能的话，可以提供一些伪代码吗？具体来说，我想知道如何使它对缓存友好。我完全不知道这些东西是什么，否则我会亲自尝试。

Answer 1

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