Algoritmo di ordinamento: differenze tra le versioni

La ricerca e l'ottimizzazione di algoritmi di ordinamento è molto importante per alcuni ambiti [[Informatica|informatici]] e per queste classi di algoritmi sono stati dimostrati svariati teoremi che ne definiscono i limiti. Il più importante è il seguente:

 

 

Questo teorema fissa il limite inferiore di complessità per gli algoritmi che si basano sul paragone di coppie di chiavi (per confronto). Nulla è noto su altri algoritmi di ordinamento, nemmeno quali possano essere. Sono stati ipotizzati (ma non prodotti) algoritmi di ordinamento totalmente [[Meccanica quantistica|quantistico]], che potrebbero avere un più basso limite inferiore di complessità.