Quicksort
Välj ett element, lägg allt mindre till vänster och allt större till höger, upprepa på båda halvorna.
Tony Hoare kom på algoritmen 1959 som 25-åring i Moskva, där han försökte sortera ord inför en maskinöversättningsuppgift. Publicerad i Communications of the ACM 1961. Genomsnittlig komplexitet är O(n log n), men värsta fallet är O(n²) — vilket inträffar precis när pivoten konsekvent hamnar i kanten, till exempel på redan sorterad indata med naiv pivotval.
Trots det sämre värstafallet slår quicksort ofta merge sort i praktiken: den sorterar på plats, har utmärkt cachelokalitet och få minnesallokeringar. Moderna standardbibliotek kör introsort — quicksort som byter till heapsort när rekursionsdjupet blir misstänkt stort, och till insertion sort för korta segment. Antikvarisk kuriosa: 2015 upptäcktes att Javas TimSort-implementation hade ett bevisbart fel i sin invariantkontroll.