Производительность встроенных сортировщиков коллекций .NET

Был задан вопрос о том, как отсортировать список. Было дано несколько методов от базового List.Sort () до List.OrderBy (). Самым смешным был метод выбора собственного выбора. Я сразу же проголосовал против, но это заставило меня задуматься; не будет ли метод Linq OrderBy (), примененный к списку, делать то же самое? мой список. OrderBy (x => x.Property) .ToList () создаст итератор, который в основном находит минимальное значение проекции в том, что осталось от коллекции, и yield возвращает его. Когда просматриваешь весь список, это сортировка выбора.

Что заставило меня задуматься; Какие алгоритмы используют встроенные сортировщики для списков, сортированных списков, перечислений и т. д., и, соответственно, следует ли избегать любого из них для больших коллекций? SortedList, поскольку он остается отсортированным по ключу, вероятно, будет использовать однопроходный InsertionSort при каждом добавлении; найти первый индекс со значением больше нового и вставить перед ним. Списки и массивы, вероятно, сами по себе MergeSort довольно эффективно, но я не знаю фактический алгоритм, стоящий за Sort (). Мы обсудили OrderBy.

То, что я знаю выше, может указывать на List.Sort () или Array. Sort () - лучший вариант для списка известного размера, и использование Linq для сортировки списка или массива в памяти не рекомендуется. Для потока действительно нет другого способа, кроме OrderBy () перечисляемого; потеря производительности смягчается тем фактом, что вы можете хранить данные в виде потока вместо того, чтобы иметь все это перед сортировкой.

РЕДАКТИРОВАТЬ:

По общему мнению, Sort () работает быстрее при конкретной реализации списка или массива. OrderBy разумен, но медленнее, потому что добавляет O (N) сложность извлечения массива из переданного перечислимого. Инициализация SortedList заканчивается O (N ^ 2) из-за того, что находится под капотом. Мораль истории: используйте List.Sort () вместо List.OrderBy (), когда у вас есть реальный List.