¿Cuál es la complejidad de tiempo de .NET list.sort()

Question

¿Cuál es la complejidad de tiempo de C# 's List<T>.Sort()

supongo que es O (n)

Pero después he buscado mucho, no he tenido ningún resultado preciso

Answer 1

http://msdn.microsoft.com/en-us/library/b0zbh7b6.aspx

Este método usa Array.Sort, que utiliza el algoritmo QuickSort. Esta implementación realiza una clasificación inestable; es decir, si dos elementos son iguales, es posible que su orden no se conserve. Por el contrario, un género estable conserva el orden de los elementos que son iguales.

En promedio, este método es una operación O (n log n), donde n es Count; en el peor de los casos, es una operación O (n^2).

Answer 2

De the documentation:

En promedio, este método es un O (n log n) la operación, donde n es Count; en el peor de los casos, es una operación O (n^2).

Esto se debe a que utiliza Quicksort. Si bien esto es típicamente O (n log n), as mentioned on Wikipedia, "Quicksort es a menudo más rápido en la práctica que otra O (n log n) algoritmos"

Answer 3

mejor que puede ser asintóticamente es O (nlogn)

Answer 4

Agregando un poco de información de la reciente adición a MSDN sobre este tema, por Framework 4.5, el método utiliza una estrategia list.sort Ordenar diferente en función del número de elementos y particiones.

Este método utiliza el método Array.Sort que se aplica el tipo introspectivo como sigue:

• Si el tamaño de la partición es menos de 16 elementos, se utiliza un algoritmo de tipo de inserción .
• Si el número de particiones excede 2 * LogN, donde N es el rango de la matriz de entrada, usa un algoritmo Heapsort.
• De lo contrario, utiliza un algoritmo Quicksort.

Esta implementación realiza un tipo inestable; es decir, si dos elementos son iguales, es posible que no se conserve su orden . En contraste, un tipo estable conserva el orden de elementos que son iguales.

En promedio, este método es una operación O (n log n) , donde n es Count; en el peor de los casos, es una operación O (n^2) .