Welcher Sortieralgorithmus ist in stl und .net-Basisbibliothek Standardsuche verwendet?

Question

Ich arbeite jetzt an einer imprived Version von Mergesort. Ich setzte es mit C ++ und C #. Dann verglichen sie mit der stl Art und array.sort (Algorithmus) ist. In C ++ Ich habe eine gleiche (manchmal besser) Ergebnis bekommt. Aber in C #, musste ich mit Zeigern unsicheren Code verwenden. Hier ist die performence nicht so viel vergleichbar mit Standardsortierung. So möchte ich das Know-
1. Welche Algorithmen werden in stl und .net Basisklassenbibliothek? (Besser mit Links) verwendet
2. Wählen Sie unsichere Codes hat performence Fragen?
3. Alle suggessions für mich in Bezug auf die Performence des neuen Algorithmus messen?

Answer 1

.NET verwendet eine Variante von Quicksort (Sedgewick des Median von 3 Quicksort).

Wenn Sie ein Experte in der Sortierung sind, würde ich überrascht, wenn Sie die eingebaute in Sort über eine breite Palette von Daten schlagen können (einschließlich zufällige, bereits bestellt und Reverse geordnete Mengen). In dem unsicheren Code Resorting ist in der Regel eine schlechte Idee ...

Answer 2

Die STL Art können über die Umsetzung ab, sondern ( wie Wikipedia sagt ) ist es in der Regel Introsort, eine Kombination aus quicksort und Heapsort. Es muss eine durchschnittliche Komplexität von O hat (n log n) Vergleiche.

Answer 3

.NET verwendet QuickSort. Sie können Reflector die Umsetzung in System.Collections.Generic.ArraySortHelper anzusehen

In den meisten Fällen werden QuickSort schneller als MergeSort laufen, obwohl die Worst-Case-Ausführungszeit länger ist. Es wird auf Standard-QuickSort einige Verbesserungen und ich denke, aber ich bin nicht sicher, wenn eine dieser Bedingungen verwendet werden.

Ich scheine STL zu erinnern QuickSort auch, aber ich bin mir nicht ganz sicher.