Algoritmo di ordinamento
Un metodo per ordinare elementi secondo una regola di confronto: il problema più studiato in tutta l'informatica.
Si può dimostrare che l'ordinamento basato su confronti non può battere O(n log n), perché n elementi hanno n! ordinamenti possibili e ogni confronto dimezza al massimo lo spazio di ricerca. Quicksort, mergesort e heapsort raggiungono tutti questo limite, con compromessi diversi in termini di memoria, stabilità e comportamento nel caso peggiore. Counting sort e radix sort aggirano il limite evitando del tutto i confronti, ma richiedono chiavi intere in un intervallo noto.
Nella pratica nessuno scrive il proprio. Le librerie standard includono ibridi affinati in decenni: introsort in C++ (un quicksort che passa a heapsort quando la ricorsione diventa profonda), Timsort in Python e Java per gli oggetti, pattern-defeating quicksort in Rust. La questione interessante è di rado quale algoritmo, ma quale confronto: la collazione del testo varia da lingua a lingua, e un comparatore incoerente produce comportamento indefinito, non semplicemente l'ordine sbagliato.