Mergesort
Si divide la lista a metà, si ordina ciascuna metà e si fondono i risultati: O(n log n) in ogni caso, senza eccezioni.
Descritto da John von Neumann nel 1945, è uno degli algoritmi più antichi ancora in produzione. La fusione scorre due liste già ordinate e prende ogni volta il minore dei due elementi in testa, in tempo lineare; la ricorsione è profonda log n; il prodotto è la complessità garantita.
Due proprietà lo rendono difficile da sostituire. È stabile: gli elementi uguali mantengono l'ordine relativo, indispensabile quando si ordina per più campi in successione. E legge solo in modo sequenziale, quindi è la scelta standard per dati troppo grandi per la memoria: gli ordinamenti esterni su disco e nastro poggiano ancora sul mergesort. Il prezzo è O(n) di memoria aggiuntiva, mentre Quicksort ne richiede quasi nessuna ma nel caso peggiore degrada a tempo quadratico. Gli ordinamenti predefiniti di Python e Java usano Timsort, un ibrido che sotto è un mergesort.