Quicksort
Ein Element wählen, alles Kleinere nach links und alles Größere nach rechts schieben, dann auf beiden Hälften wiederholen.
Tony Hoare entwickelte den Algorithmus 1959 im Alter von 25 Jahren in Moskau, als er Wörter für eine Übung zur maschinellen Übersetzung sortieren wollte. Veröffentlicht 1961 in Communications of the ACM. Die durchschnittliche Komplexität liegt bei O(n log n), der schlechteste Fall aber bei O(n²) — und der tritt genau dann ein, wenn der Pivot konsequent an einem Rand landet, etwa bei bereits sortierten Eingabedaten und naiver Pivotwahl.
Trotz des schlechteren Worst-Case schlägt Quicksort in der Praxis oft Mergesort: Er sortiert direkt im Speicher, hat exzellente Cache-Lokalität und braucht kaum Allokationen. Moderne Standardbibliotheken setzen auf Introsort — Quicksort, das bei verdächtig tiefer Rekursion auf Heapsort umschaltet und bei kurzen Abschnitten auf Insertion Sort. Kuriosum am Rande: 2015 wurde nachgewiesen, dass Javas TimSort-Implementierung einen echten Fehler in ihrer Invariantenprüfung hatte.