內置 .NET 集合分類器的性能
有一個關於如何對列表進行排序的問題。從基本的 List.Sort() 到 List.OrderBy() 有幾種方法。最可笑的是roll-your-own-SelectionSort。我立即投了反對票，但這讓我思考；應用於列表的 Linq 的 OrderBy() 不會做同樣的事情嗎？myList.OrderBy(x=>x.Property).ToList() 將產生一個迭代器，它基本上在集合的左側找到投影的最小值，並返回它。當遍歷整個列表時，這是一個選擇排序。
這讓我想到；Lists、SortedLists、Enumerables 等的內置排序器使用什麼算法，並且通過擴展，對於大型集合是否應該避免使用它們中的任何一種？SortedList，因為它保持按鍵排序，可能會在每次添加時使用單遍 InsertionSort；找到值大於新索引的第一個索引，並在它之前插入。列表和數組本身可能非常有效地合併排序，但我不知道 Sort() 背後的實際算法。我們已經討論了 OrderBy。
我在上面所知道的似乎表明 List.Sort() 或 Array.Sort() 是已知大小列表的最佳選擇，不鼓勵使用 Linq 對記憶體中的列表或數組進行排序。對於流，除了 OrderBy() 列舉之外真的沒有其他方法了；您可以將數據保留為流，而不必在對其進行排序之前將其全部保存，從而減輕了性能損失。
編輯：
普遍的共識是，給定 List 或 Array 的具體實現，Sort() 會更快。OrderBy 是合理的，但速度較慢，因為它增加了從傳遞的列舉中提取數組的 O(N) 複雜性。SortedList 初始化最終是 O(N^2) 因為引擎蓋下的東西。故事的道德，當你有一個實際的列表時，使用 List.Sort() 而不是 List.OrderBy()。
Enumerable.OrderBy() 將 IEnumerable<> 放入一個數組並使用快速排序。O(n) 儲存要求。它由 System.Core.dll 中的內部類完成，
EnumerableSort<TElement>.QuickSort(). 儲存成本使得簡單地對列表進行排序（如果有的話）沒有競爭力，因為 List<> 就地排序。Linq 通常通過使用 is 運算符檢查 IEnumerable 的真實功能來進行優化。在這裡不起作用，因為 List<>.Sort 是破壞性的。List<>.Sort 和 Array.Sort 使用就地快速排序。
SortedList<> 的插入複雜度為 O(n)，超過了查找插入點的 O(log(n)) 複雜度。因此，將 N 個未排序的項目放入其中將花費 O(n^2)。SortedDictionary<> 使用紅黑樹，插入複雜度為 O(log(n))。因此 O(nlog(n)) 來填充它，與攤銷快速排序相同。