Límite inferior para algoritmos de clasificación basados ​​en comparación

El problema de la clasificación se puede ver de la siguiente manera. 

Entrada: Una secuencia de n números < a ₁ , a ₂ , . . . , una _n >. 
Salida: Una permutación (reordenación) < a ‘ ₁ , a ‘ ₂ , . . . , a ‘ _n > de la secuencia de entrada tal que a ‘ ₁ <= a ‘ ₂ ….. <= a’ _n . 

Un algoritmo de clasificación se basa en la comparación si utiliza operadores de comparación para encontrar el orden entre dos números. Los tipos de comparación se pueden ver de manera abstracta en términos de árboles de decisión. Un árbol de decisión es un árbol binario completo que representa las comparaciones entre elementos realizadas por un algoritmo de clasificación particular que opera en una entrada de un tamaño determinado. La ejecución del algoritmo de clasificación corresponde a trazar un camino desde la raíz del árbol de decisión hasta una hoja. En cada Node interno se realiza una comparación a _i <= a _{j .} El subárbol izquierdo dicta las comparaciones subsiguientes para a _i <= a _j , y el subárbol derecho dicta las comparaciones subsiguientes paraai > aj . _{_ _} Cuando llegamos a una hoja, el algoritmo de clasificación ha establecido el orden. Entonces podemos decir lo siguiente sobre el árbol de decisión. 

1) Cada uno de los n ! las permutaciones en n elementos deben aparecer como una de las hojas del árbol de decisión para que el algoritmo de clasificación las clasifique correctamente. 

2) Sea x el número máximo de comparaciones en un algoritmo de clasificación. La altura máxima del árbol de decisión sería x. Un árbol con una altura máxima x tiene como máximo 2^x hojas. 

Después de combinar los dos hechos anteriores, obtenemos la siguiente relación. 
 

  
      n!  <= 2^x

 Taking Log on both sides.
      log2(n!)  <= x

 Since log2(n!)  = Θ(nLogn),  we can say
      x = Ω(nLog2n)

Por lo tanto, cualquier algoritmo de clasificación basado en comparación debe realizar al menos nLog ₂ n comparaciones para clasificar la array de entrada, y Heapsort y merge sort son clasificaciones de comparación asintóticamente óptimas. 

Referencias:  
Introducción a los algoritmos, por Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest y Clifford Stein