Ordinamento a confronto

Gli algoritmi trattati saranno basati sul confronto attraverso una tecnica incrementale, cioè utilizzando la soluzione al problema grande $k$ per risolvere quello grande $k+1$.

Al momento non esiste alcun algoritmo basato sul confronto con complessità inferiore a $O(n\log n)$.

Proprietà

Un algoritmo è detto in loco quando lo spazio richiesto dall'algoritmo è costante.

Viene anche detto stabile se l'ordine degli elementi con chiavi uguali rimane invariato dopo l'ordinamento.