Sorteeralgoritme
Een methode om elementen te ordenen volgens een vergelijkingsregel — het grondigst bestudeerde probleem uit de hele informatica.
Sorteren op basis van vergelijkingen kan aantoonbaar niet beter dan O(n log n), omdat n elementen n! mogelijke volgordes hebben en elke vergelijking de zoekruimte slechts halveert. Quicksort, mergesort en heapsort halen die grens allemaal, met verschillende afwegingen in geheugen, stabiliteit en worstcasegedrag. Counting sort en radix sort ontsnappen aan de grens door helemaal niet te vergelijken, maar vereisen sleutels die gehele getallen in een bekend bereik zijn.
In de praktijk schrijft niemand er zelf een. Standaardbibliotheken leveren hybriden die decennia zijn verfijnd — introsort in C++ (quicksort die overschakelt op heapsort als de recursie te diep wordt), Timsort in Python en Java voor objecten, pattern-defeating quicksort in Rust. De interessante vraag is zelden welk algoritme, maar welke vergelijking: tekst-collatie verschilt per taal, en een inconsistente vergelijker levert ongedefinieerd gedrag op, niet slechts de verkeerde volgorde.