对小型数组（少于 32 或 64 个元素）进行快速稳定排序

Question

常识认为，对于足够小的数组，插入排序是最好的。例如，Timsort对最多 64 个元素的数组使用（二进制）插入排序；来自维基百科：

一些分治算法（例如快速排序和合并排序）通过递归地将列表划分为较小的子列表然后进行排序来排序。在实践中，这些算法的一个有用的优化是使用插入排序对小子列表进行排序，因为插入排序优于这些更复杂的算法。插入排序具有优势的列表的大小因环境和实现而异，但通常在八到二十个元素之间。

这实际上是正确的吗？还有更好的选择吗？

如果这在很大程度上取决于平台，我对 .NET 最感兴趣。

Answer 1

是的，这就是我在算法课上学到的，这也是 C++ STL 中排序的实现方式。来自维基百科：

2000 年 6 月 SGI C++ 标准模板库 stl_algo.h 不稳定排序的实现使用 Musser introsort 方法，其中递归深度切换到作为参数传递的堆排序、中值 3 的主元选择和 Sedgewick 最终插入排序传递。切换到简单插入排序的元素阈值为 16。

去年我做了一些非正式的性能测试，C++ STL std::sort 的速度大约是 .NET 中 Array.Sort 的两倍。我不知道 .NET Array.Sort 是如何实现的，但在 .NET 中，数组中的访问需要进行边界检查，这与 C++ 不同，这在很大程度上可以解释性能差异。