Ciao,

è corretto quello che dici, cioè effettivamente il limite asintotico inferiore per gli algoritmi di ordinamento basati su confronti è nlogn. Altri algoritmi di ordinamento non basati su confronti (come il Counting sort o il Radix sort) riescono a raggiungere anche complessità lineari ma questo soltanto a condizioni particolari che ne limitano abbastanza il campo di applicabilità (è proprio questo il loro svantaggio, se non ce l'avessero sarebbero preferibili a quelli a complessità nlogn).

In ogni caso la dimostrazione del teorema sulla complessità asintotica inferiore degli algoritmi di ordinamento basati su confronto non è proprio semplice. Ti posso consigliare questo pdf:

http://cvprlab.uniparthenope.it/staf...2009/ASD-8.pdf

nelle cui prime 28 pagine viene dimostrato il teorema (si tratta di appunti di lezione del corso di "Algoritmi e Strutture Dati" della Parthenope di Napoli, principalmente sono riassunti del libro "Introduzione agli algoritmi e strutture dati" che è eccellente per lo studio della materia http://www.catalogo.mcgraw-hill.it/c...p?item_id=1920 ).

Spero ti possa essere d'aiuto...