Warum ist Quicksort im Durchschnitt schneller als andere?

Worst Case für schnelle Sortierung ist eigentlich schlechter als Heapsort und Mergesort, aber Quicksort ist im Durchschnitt schneller.

Warum, es wird einige Zeit dauern zu erklären und damit werde ich auf Skiena, Das Design-Handbuch für den Algorithmus.

Ein Zitat, das den Quicksort vs merge / heapsort zusammenfasst:

  

Wenn mit Algorithmen der gleichen asymptotischen Komplexität konfrontiert wird, Implementierung   Details und Systemquirks wie Cache-Leistung und Speichergröße können   erweisen sich als der entscheidende Faktor.   Was wir sagen können ist, dass Experimente zeigen, dass wo richtig umgesetzt wurde   Quicksort ist gut implementiert, es ist in der Regel 2-3 mal schneller als Mergesort oder   Heapsort. Der Hauptgrund ist, dass die Operationen in der innersten Schleife sind   einfacher. Aber ich kann nicht mit dir streiten, wenn du mir nicht glaubst, wenn ich Quicksort sage   schneller. Es ist eine Frage, deren Lösung außerhalb der analytischen Werkzeuge liegt, die wir verwenden.   Der beste Weg zu erzählen ist, sowohl Algorithmen als auch Experimente zu implementieren.

Wikipedia schlägt vor :

  

In der Regel ist Quicksort signifikant   schneller in der Praxis als andere O (nlogn)   Algorithmen, weil seine innere Schleife kann   in den meisten Fällen effizient implementiert werden   Architekturen und in den meisten realen Welt   Daten, ist es möglich, Design zu machen   Entscheidungen, die die Wahrscheinlichkeit minimieren   von quadratischer Zeit erfordern.   Darüber hinaus neigt Quicksort zu machen   ausgezeichnete Nutzung des Speichers   Hierarchie, die den vollkommenen Vorteil von   virtueller Speicher und verfügbare Caches.   Obwohl Quicksort kein In-Place ist   Sortieren und verwendet Hilfsspeicher, ist es   Sehr gut geeignet für moderne Computer   Architekturen.

Sehen Sie sich auch einen Vergleich mit anderen Sortieralgorithmen auf derselben Seite an.

Siehe auch Warum ist Quicksort besser als? andere Sortieralgorithmen in der Praxis? auf der CS-Site.

Timsort könnte ein Bessere Option, da sie für die Art von Daten optimiert ist, die beim Sortieren im Allgemeinen in der Sprache Python angezeigt werden, wo Daten häufig eingebettete" Läufe "vorsortierter Elemente enthalten. Es wurde kürzlich auch von Java übernommen.