在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，但我並不完全確定。