共同的看法认为，对于足够小的阵列插入排序是最好的。例如， Timsort 用途（二进制）插入排序为数组最多64元;从维基百科：

The common wisdom says that for small enough arrays insertion sort is the best. E.g., Timsort uses (binary) insertion sort for arrays up to 64 elements; from Wikipedia:

一些分而治之算法，如快速排序和归并排序递归划分表成更小的子列表然后将其排序。这些算法在实践中的一个有用的优化是使用插入排序进行排序小型子列表，如插入排序优于这些更复杂的算法。列表的量插入排序具有如下优点的大小受环境和实现不同而不同，但通常是8和20元件之间。

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.

这是实际上是正确的？有没有更好的方法？

Is this actually correct? Are there any better alternatives?

在这种情况下，取决于显著平台上，我最感兴趣的是.NET。

In case this depends significantly on platform, I am most interested in .NET.

推荐答案

是的，这是我学到的东西在我的算法类，这还怎么样在C ++ STL的实现。维基百科：

Yes, this is what I've learned in my algorithms classes, and this is also how sort is implemented in the C++ STL. From Wikipedia:

2000年6月SGI的C ++标准   模板库stl_algo.h   执行不稳定排序用途   与该马瑟introsort方法   递归深度切换到堆排序   作为参数传递，中位数的3   支点选择和塞奇威克   最后插入排序通过。元素   阈值切换至简单   插入排序为16。

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 ::排序是大约快一倍的Array.Sort在.NET。我不知道该怎么.NET的Array.Sort实现，但在.NET中，在阵列的访问需要范围检查，不象在C ++中，这可以在很大程度上解释的性能差异。

I did some informal performance tests last year and C++ STL std::sort was about twice as fast as Array.Sort in .NET. I don't know how .NET Array.Sort is implemented, but in .NET, an access in an array requires a bounds check, unlike in C++, which could largely account for the performance difference.