Clasificación de Python complejidad en la lista ordenada

¿Cuál es la complejidad de sort(already_sorted_list) en Python? ¿Python comprueba si el iterable dado está ordenado, o tengo que hacerlo yo solo? No pude encontrarlo en ningún lugar en la documentación.

Esto es totalmente dependiente de la implementación. Todo lo que Python garantiza es que el algoritmo de clasificación incorporado es estable (los elementos que comparan igual conservan su ordenamiento relativo). Una implementación podría incluso usar un ordenamiento de burbuja estable si quisiera …

Cpython utiliza TimSort (un híbrido de tipo de inserción y fusión) que creo que tiene complejidad O (N) si la entrada ya está ordenada. )).

Y si tiene curiosidad por la implementación, el código fuente tiene una descripción muy buena.

El género de Python se llama timsort . Su rendimiento promedio es O (nlog (n)). Se desempeña realmente bien con listas pre-ordenadas porque su implementación está diseñada para buscar ejecuciones de elementos ordenados en la lista.