Welcher Sortieralgorithmus wird von der STL-Liste verwendet :: sort()?

Question

Ich habe eine Liste von zufälligen ganzen Zahlen. Ich frage mich, welcher Algorithmus von der Methode list :: sort() verwendet wird. Z.B. in dem folgenden Code:

list<int> mylist; 

// ..insert a million values 

mylist.sort(); 

EDIT: Siehe auch this more specific question.

Answer 1

Der Standard erfordert keinen bestimmten Algorithmus, nur dass er stabil sein muss und dass er die Sortierung unter Verwendung von ungefähr N Ig N Vergleichen vervollständigt. Dies ermöglicht zum Beispiel eine Zusammenführung-Sortierung oder eine verkettete Liste einer schnellen Sortierung (entgegen der landläufigen Meinung, schnelle Sortierung ist nicht notwendig instabil, obwohl die am häufigsten verwendete Implementierung für Arrays ist). Die kurze Antwort ist, dass in den meisten aktuellen Standardbibliotheken std::sort als Intro-Sortierung (introspektive Sortierung) implementiert ist, was im Grunde ein Quicksort ist, der seine Rekursionstiefe verfolgt und zu a wechselt Heapsort (normalerweise langsamer, aber garantiert O (n log n) -Komplexität), wenn der Quicksort eine zu tiefe Rekursion verwendet. Introsort wurde relativ spät erfunden (Ende der 1990er Jahre). Ältere Standardbibliotheken verwendeten in der Regel stattdessen ein Quicksort.

stable_sort existiert, weil zum Sortieren von Array artigen Behälter, die meisten der am schnellsten Sortieralgorithmen instabil sind, so dass der Standard umfasst sowohl std::sort (schnell, aber nicht unbedingt stabil) und std::stable_sort (stabil, aber oft etwas langsamer).

Beide erwarten jedoch normalerweise Iteratoren mit wahlfreiem Zugriff und funktionieren (wenn überhaupt) nur schlecht mit einer verknüpften Liste. Um eine angemessene Leistung für verknüpfte Listen zu erhalten, enthält der Standard list::sort. Für eine verkettete Liste gibt es jedoch keinen solchen Kompromiss - es ist ziemlich einfach, eine Merge-Sortierung zu implementieren, die sowohl stabil als auch praktisch ist. Als solche benötigten sie nur eine sort Mitgliedsfunktion, die stabil sein muss.

Answer 2

Es ist vollständig Implementierung definiert. Das einzige, was der Standard darüber sagt, ist, dass seine Komplexität 0 (n lg n) ist und dass die Sortierung stabil ist. Das heißt, die relative Reihenfolge der gleichen Elemente wird garantiert nicht nach dem Sortieren geändert.

std::list sort member function wird normalerweise mithilfe einer Art merge sort implementiert, da merge sort stabil ist und Zusammenführungen wirklich sehr günstig sind, wenn Sie mit verknüpften Listen arbeiten.

Hoffnung, das hilft :)

Answer 3

Obwohl es Implementierung/Vertrieb abhängig ist, aber die meisten Implementierung Ich weiß, verwendet Introsort deren beste & worst case Komplexität ist O (n log n).

Referenz: http://en.wikipedia.org/wiki/Introsort