.net - 小数组(少于 32 或 64 个元素)的快速稳定排序

Question

常识说，对于足够小的数组，插入排序是最好的。例如，Timsort对最多 64 个元素的数组使用(二进制)插入排序；来自 Wikipedia :

Some divide-and-conquer algorithms such as quicksort and mergesort sort by recursively dividing the list into smaller sublists which are then sorted. A useful optimization in practice for these algorithms is to use insertion sort for sorting small sublists, as insertion sort outperforms these more complex algorithms. The size of list for which insertion sort has the advantage varies by environment and implementation, but is typically between eight and twenty elements.

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

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

Answer 1

是的，这就是我在我的算法类(class)中学到的，这也是在 C++ STL 中如何实现排序的。来自维基百科:

The June 2000 SGI C++ Standard Template Library stl_algo.h implementation of unstable sort uses the Musser introsort approach with the recursion depth to switch to heapsort passed as a parameter, median-of-3 pivot selection and the Sedgewick final insertion sort pass. The element threshold for switching to the simple insertion sort was 16.

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