Über Pythons eingebaute sort()-Methode

Question

Welcher Algorithmus ist in den sort() Methode in Python verwenden? Ist es möglich, einen Blick auf den Code für diese Methode zu werfen?

Answer 1

Aber sicher! Der Code ist aquí , beginnend mit der Funktion islt und das schon eine ganze Weile;-). Wie der Kommentar von Chris andeutet, handelt es sich um C-Code. Sie werden auch lesen wollen este Textdatei für eine textliche Erklärung, Ergebnisse usw. usw.

Wenn Sie lieber Java-Code als C-Code lesen, können Sie sich Joshua Blochs Implementierung von timsort in und für Java ansehen (Joshua ist auch derjenige, der 1997 das modifizierte mergesort implementiert hat, das immer noch in Java verwendet wird, und man kann hoffen, dass Java irgendwann zu seiner jüngsten Portierung von timsort wechselt).

Einige Erklärungen zur Java-Portierung von timsort sind aquí ist der Unterschied aquí (mit Zeigern auf alle benötigten Dateien), die Schlüsseldatei ist aquí -- FWIW, ich bin zwar ein besserer C-Programmierer als Java-Programmierer, aber in diesem Fall finde ich Joshuas Java-Code insgesamt lesbarer als Tims C-Code;-).

Answer 2

Ich wollte nur einen sehr hilfreichen Link nachliefern, den ich in Alex' ansonsten umfassender Antwort vermisst habe: Eine ausführliche Erklärung von Pythons timsort (mit grafischen Darstellungen!).

(Ja, der Algorithmus ist im Wesentlichen bekannt als Timsort jetzt)

Answer 3

In frühen Python-Versionen implementierte die Sortierfunktion eine modifizierte Version von Quicksort. Diese wurde jedoch als instabil erachtet und ab Version 2.3 wurde auf einen adaptiven Mergesort-Algorithmus umgestellt.