Confronto algoritmo di ordinamento Complessità

Question

Perché è il limite inferiore per la complessità temporale di confronto basato su algoritmi di ordinamento O (n log n)?

Answer 1

http://en.wikipedia.org/wiki/Comparison_sort#Number_of_comparisons_required_to_sort_a_list

risponde a questa domanda abbastanza bene, credo.

Answer 2

In breve, perché si deve guardare a ogni elemento che è O (n). Per ciascuno di tali elementi si guarda, si deve scoprire se la sua nel giusto ordine, che è nel migliore dei casi O (log n) (ricerca binaria per esempio). Quindi la somma netta diventa O (n log n)