algorithm - 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 排序可能取决于实现，但（正如维基百科所说）它通常是 introsort，快速排序和堆排序的组合。它必须具有 O(n log n) 比较的平均复杂度。

Answer 3

.NET 使用快速排序。您可以使用Reflector查看 System.Collections.Generic.ArraySortHelper 中的实现

在大多数情况下，QuickSort 会比 MergeSort 运行得更快，即使最坏情况下的执行时间更长。我认为标准 QuickSort 也有一些改进，但我不确定是否使用了其中的任何一个。

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