Ordenar un arreglo

Consideremos el problema de ordenar $A[1,n]$. Ordenar implica aplicar una permutación $\pi$ al rango $[1,n]$ de modo que $A$ quede ordenado. Esto significa que la permutación original que traían los elementos de $A$, $\rho$, es la inversa de $\pi$. Para cada $\rho$ posible, un algoritmo correcto de ordenamiento debe aplicar un conjunto distinto de operaciones $\pi = \rho^{-1}$. Un algoritmo que procede únicamente por comparaciones puede entonces utilizarse para codificar la permutación $\pi$ (o $\rho$) de la misma manera que en el ejemplo anterior: los resultados de las comparaciones que va realizando (ignorando las modificaciones que hace al arreglo o cualquier otra operación) deben ser distintas para cada input posible $\rho$.

Dado que existen $n!$ posibles permutaciones en las que $A$ puede presentarse, el algoritmo necesita realizar al menos $\log_2 (n!)$ comparaciones para poder realizar un conjunto de acciones distinto para cada una de ellas. Por la aproximación de Stirling, $\log_2 (n!) = n\log_2 n - O(n)$. Dicho más gruesamente, para ordenar por comparaciones se necesita tiempo $\Omega(n\log n)$.