在stl和.net基本库默认搜索中使用哪种排序算法？

Question

我现在正在处理合并排序的受侵害版本。我用C++和C＃实现了它。然后分别将它们与stl sort和array.sort（）算法进行比较。在C++中，我得到了相等（有时更好）的结果。但在C＃中，我不得不使用不安全的代码来使用指针。在这里，性能与默认排序并无太大的可比性。所以，我想知道 -

1.在stl和.net基类库中使用哪些算法？（更好的链接）
2.不安全的代码是否存在性能问题？
3.对于测量新算法性能的任何建议？

Answer 1

.NET使用Quicksort的变体（Sedgewick的中位数为3的Quicksort）。除非你是排序专家，否则如果你可以击败内置的对各种数据进行排序（包括随机，已经排序和反向排序的排序），我会感到惊讶。采用不安全的代码通常是一个坏主意......

Answer 2

STL排序可能取决于实现，但（as wikipedia says）它通常是introsort，quicksort和heapsort的组合。它必须具有O（n log n）比较的平均复杂度。

Answer 3

.NET使用QuickSort。您可以使用Reflector查看System.Collections.Generic.ArraySortHelper中的实现

在大多数情况下，即使最差情况下执行时间较长，QuickSort的运行速度也会比MergeSort快。标准QuickSort也有一些改进，我认为，但我不确定是否使用了这些改进。

我似乎还记得使用QuickSort的STL，但我并不完全确定。