Какой алгоритм сортировки используется LINQ "OrderBy"?

Очевидно, что LINQ "OrderBy" изначально был указан как неустойчивый, но ко времени Orca он был указан как стабильный. Не все документы были обновлены соответственно - рассмотрите эти ссылки:

Но если LINQ OrderBy теперь "стабилен", то это означает, что он не использует quicksort (который по своей сути неустойчив), хотя некоторые документы (например, книга Трой) говорят, что это так. Поэтому мой вопрос: если не quicksort, то какой алгоритм использует LINQ orderBy?

Ответы

Ответ 1

Для LINQ to Objects это стабильная быстрая сортировка, которая используется. Для любого другого типа LINQ он остался в основной реализации.

Ответ 2

Загрузите отражатель, откройте System.Linq.EnumerableSorter показывает, что Linq2Objects использует быструю сортировку

Ответ 3

Используется Quicksort, но причина его стабильности заключается в том, что индексы каждой пары элементов сравниваются, если все ключи проверяются равными.

Другими словами, вы можете сделать любую быструю сортировку устойчивой, включив в функцию компаратора сравнение исходных индексов этих двух элементов в качестве резервной копии.

Источник: http://referencesource.microsoft.com/#System.Core/System/Linq/Enumerable.cs,1395017e067e5a34

Ответ 4

Я понимаю, что OrderBy переводится в SQL, который выполняет сортировку в базе данных. По крайней мере, в случае LINQ to SQL