Очевидно, что LINQ "OrderBy" изначально был указан как неустойчивый, но ко времени Orca он был указан как стабильный. Не все документы были обновлены соответственно - рассмотрите эти ссылки:
Но если LINQ OrderBy теперь "стабилен", то это означает, что он не использует quicksort (который по своей сути неустойчив), хотя некоторые документы (например, книга Трой) говорят, что это так. Поэтому мой вопрос: если не quicksort, то какой алгоритм использует LINQ orderBy?
Для LINQ to Objects это стабильная быстрая сортировка, которая используется. Для любого другого типа LINQ он остался в основной реализации.
Загрузите отражатель, откройте System.Linq.EnumerableSorter показывает, что Linq2Objects использует быструю сортировку
Используется Quicksort, но причина его стабильности заключается в том, что индексы каждой пары элементов сравниваются, если все ключи проверяются равными.
Другими словами, вы можете сделать любую быструю сортировку устойчивой, включив в функцию компаратора сравнение исходных индексов этих двух элементов в качестве резервной копии.
Источник: http://referencesource.microsoft.com/#System.Core/System/Linq/Enumerable.cs,1395017e067e5a34
Я понимаю, что OrderBy переводится в SQL, который выполняет сортировку в базе данных. По крайней мере, в случае LINQ to SQL