Что такое временная сложность .NET List.sort()

Ответ 1

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

Этот метод использует Array.Sort, который использует алгоритм QuickSort. Эта реализация выполняет нестабильную сортировку; то есть, если два элемента равны, их порядок может не сохраниться. Напротив, устойчивая сортировка сохраняет порядок равных элементов.

В среднем этот метод является операцией O (n log n), где n - Count; в худшем случае это операция O (n ^ 2).

Ответ 2

Из документация:

В среднем этот метод является операцией O (n log n), где n - Count; в худшем случае это операция O (n ^ 2).

Это потому, что использует Quicksort. Хотя это обычно O (n log n), как упоминалось в Википедии, "Quicksort быстрее на практике, чем другие O (n log n) алгоритмы"

Ответ 3

Добавляя некоторую информацию из недавнего добавления в MSDN в этом разделе, для Framework 4.5 метод List.Sort использует другую стратегию сортировки в зависимости от количества элементов и разделов.

Этот метод использует метод Array.Sort, который применяет интроспективный вид следующим образом:

• Если размер раздела меньше 16 элементов, он использует вставку алгоритм сортировки.
• Если количество разделов превышает 2 * LogN, где N - это диапазон входного массива, он использует алгоритм Heapsort.
• В противном случае он использует алгоритм Quicksort.

Эта реализация выполняет неустойчивый вид; то есть, если два элемента равны, их порядок может не сохраниться. Напротив, устойчивая сортировка сохраняет порядок элементов, которые равны.

В среднем этот метод представляет собой O (n log n) операция, где n - граф; в худшем случае это O (n ^ 2) операции.

Ответ 4

лучше всего это может быть асимптотически O (nlogn)