上次我們分析了Array.Sort<T>方法的實現方式，並了解到類庫會為一些特例而使用高性能的排序方式——int數組便是這樣一例，因此從測試結果上來看其性能特別高。不過從數據上看，即便是在普通的情況下，Array.Sort<T>的性能也比LINQ排序要高。不過也有朋友從測試中得出的結論正好相反，這又是為什麼呢？那麼現在，我們再來分析一下LINQ排序的實現方式吧，希望這樣可以了解到兩者性能差別的秘密。
只可惜，LINQ排序的代碼在System.Core.dll程序集中，微軟沒有發布這部分源代碼，我們只得使用.Net Reflector來一探究竟了。
LINQ排序接口的定義、使用及擴展
所謂LINQ排序，便是使用定義在System.Linq.Enumerable類中的幾個擴展方法，它們是：
public static IOrderedEnumerable<TSource> OrderBy<TSource, TKey>(
this IEnumerable<TSource> source, Func<TSource, TKey> keySelector);
public static IOrderedEnumerable<TSource> OrderBy<TSource, TKey>(
this IEnumerable<TSource> source, Func<TSource, TKey> keySelector, IComparer<TKey> comparer);
public static IOrderedEnumerable<TSource> OrderByDescending<TSource, TKey>(
this IEnumerable<TSource> source, Func<TSource, TKey> keySelector);
public static IOrderedEnumerable<TSource> OrderByDescending<TSource, TKey>(
this IEnumerable<TSource> source, Func<TSource, TKey> keySelector, IComparer<TKey> comparer);為了使用時的方便，我往往會補充一些額外的接口，例如：
public static IOrderedEnumerable<TSource> OrderBy<TSource, TKey>(
this IEnumerable<TSource> source, Func<TSource, TKey> keySelector, bool decending)
{
return decending ?
source.OrderByDescending(keySelector) :
source.OrderBy(keySelector);
}這樣在使用時，便可以使用一個布爾值來表示排序的方向（升序或是降序）而不需要從兩個方法之間“手動”選擇一個。此外，構造一個IComparer<TKey>類型也實在有些麻煩，於是我按照Array.Sort<T>的做法重新繼續擴展了一個使用委托對象作為“比較器”的接口：
public static IOrderedEnumerable<TSource> OrderBy<TSource, TKey>(
this IEnumerable<TSource> source, Func<TSource, TKey> keySelector, Comparison<TKey> compare, bool decending)
{
return decending ?
source.OrderByDescending(keySelector, new FunctorComparer<TKey>(compare)) :
source.OrderBy(keySelector, new FunctorComparer<TKey>(compare));
}至於FunctorComparer類的實現，由於過於簡單就省略了吧，貼出來也只是占用地方而已。有了這個接口，在排序的時候我們就可以這樣使用了：
employee.OrderBy(p => p.Manager, (m1, m2) => ... /* 比較邏輯 */, false);不過，無論是哪個接口、重載還是擴展，它的（除this外）的第一個參數便是keySelector，它的含義便是選擇（select）出排序的“依據”。這個參數不可省略（除非您提供擴展），因此即便是int數組這樣的類型，需要排序時也必須指定“自己”為排序依據：
intArray.OrderBy(i => i);這也是LINQ排序和Array.Sort<T>的本質區別之一。
OrderedEnumerable的實現
無論是哪個接口，最終創建的都是OrderedEnumerable<TElement, TKey>類型，例如：
public static IOrderedEnumerable<TSource> OrderBy<TSource, TKey>(
this IEnumerable<TSource> source, Func<TSource, TKey> keySelector)
{
return new OrderedEnumerable<TSource, TKey>(source, keySelector, null, false);
}OrderedEnumerable<TElement, TKey>的含義是“根據TKey排序TElement序列的結果”，它的構造函數僅僅是保留傳入的參數：
internal OrderedEnumerable(
IEnumerable<TElement> source, Func<TElement, TKey> keySelector, IComparer<TKey> comparer, bool descending)
{
// 省略參數校驗
base.source = source;
this.parent = null;
this.keySelector = keySelector;
this.comparer = (comparer != null) ? comparer : ((IComparer<TKey>) Comparer<TKey>.Default);
this.descending = descending;
}可見，如果您沒有提供比較器，類庫會自動選用Comparer<TKey>.Default進行比較。這個類會盡可能地尋找可用的比較方式，在“萬不得已”的情況下只得跑出異常。如果您對它的實現感興趣可以自行閱讀代碼——甚至無需使用.Net Reflector。
事實上，在OrderedEnumerable<TElement, TKey>中並沒有提供排序等關鍵性功能，它只是override了基類的GetEnumerableSorter方法，用於提供一個“排序器”。它的基類是OrderdEnumerable<TElement>，其含義是“排序TElement序列的結果”，它並不涉及到“排序方式”，而只是提供了一個抽象方法用於獲得一個“排序器”——沒錯，這就是它的子類，如OrderedEnumerable<TElement, TKey>的職責了（還記得TKey的含義嗎：“根據TKey進行排序”）。
不過，事實上除了OrderdEnumerable<TElement, TKey>以外也沒有其他子類了，由於這些都是internal類型，因此我認為這樣有些“過渡設計”。根據我們昨天“人肉反編譯”的結果，可以得到OrderedEnumerable<TElement>的完整實現：
internal abstract class OrderedEnumerable<TElement> : IEnumerable<TElement>...
{
internal IEnumerable<TElement> source;
internal abstract EnumerableSorter<TElement> GetEnumerableSorter(EnumerableSorter<TElement> next);
public IEnumerator<TElement> GetEnumerator()
{
var buffer = new Buffer<TElement>(this.source);
if (buffer.count <= 0) yIEld break;
var sorter = this.GetEnumerableSorter(null);
var map = sorter.Sort(buffer.items, buffer.count);
for (var i = 0; i < buffer.count; i++)
{
yIEld return buffer.items[map[i]];
}
}
...
}與我們平時接觸到的排序算法不同，EnumerableSorter的Sort方法並不改變原數組，它只是生成根據buffer.items數組生成一個排序之後的“下標序列”——即map數組。當外部需要輸出排序後的序列時，OrderedEnumerable<TElement>才會根據map中的下標順序，依次輸出buffer.items數組中的元素。
請注意，到目前為止我們還是沒有接觸到最終的排序實現。換句話說，現在我們還是不清楚LINQ排序性能高（或低）的關鍵。
排序實現：EnumerableSorter
LINQ排序的實現關鍵還是在於EnumerableSorter<TElement>，我們且看其Sort代碼：
internal abstract class EnumerableSorter<TElement>
{
internal abstract int CompareKeys(int index1, int index2);
internal abstract void ComputeKeys(TElement[] elements, int count);
PRivate void QuickSort(int[] map, int left, int right)
{
...
}
internal int[] Sort(TElement[] elements, int count)
{
this.ComputeKeys(elements, count);
int[] map = new int[count];
for (int i = 0; i < count; i++)
{
map[i] = i;
}
this.QuickSort(map, 0, count - 1);
return map;
}
}從之前的分析中得知，Sort方法的作用是返回一個排好序的下標數組。它會調用ComputeKeys抽象方法“事先”進行Key（也就是排序依據）的計算。然後再使用快速排序來排序map數組。在QuickSort中，它使用CompareKeys方法來獲得“兩個下標”所對應的元素的先後順序。僅此而已，沒什麼特別的。甚至我在這裡都不打算分析ComputeKeys和CompareKeys兩個方法的實現，因為他們實在過於直接：前者會把source序列中的元素依次調用keySelector委托，以此獲得一個與source對應的TKey數組，而後者便是根據傳入的下標來比較TKey數組中對應的兩個元素的大小。
不過，我還是強烈建議您閱讀一下EnumerableSorter<TElement>及其子類EnumerableSorter<TElement, TKey>的實現，以此了解LINQ to Object是如何優雅地支持以下表達式的：
var sorted = from p in people
orderby p.Age
orderby p.ID descending
select p;這個表達式的含義是“將Person序列首先根據Age屬性進行升序排列，如果Age相同則再根據ID降序排”——類庫在實現時使用了類似於“職責鏈模式”的做法，頗為美觀。
LINQ排序與Array.Sort<T>的性能比較
如果您仔細閱讀EnuerableSorter的QuickSort方法，會發現它使用的快速排序算法並不“標准”。快速排序的性能關鍵之一是選擇合適的pivot元素，但是QuickSort方法總是選擇最中間的元素——(left + right) / 2。此外，它也沒有在元素小於一定阈值時使用更高效的插入排序。因此，從理論上來說，QuickSort方法使用的快速排序算法，其性能不如Array.Sort<T>。
不過，根據姜敏兄的測試結果，LINQ排序的性能超過Array.Sort<T>，這又是怎麼回事呢？事實上，雖然姜兄的這個測試存在很大的問題（代碼寫錯了），最後得到的結論“性能高低和元素類型有關”的結論也不確切，但是它也的確能體現一些問題。這個問題事實上已經由Ivony...老大解釋過了，不過為了信息完整思維連貫，我在這裡再進行詳細說明一下。
從理論上來說，Array.Sort<T>和LINQ排序的時間復雜度是相同的，因此性能“似乎不會有太大不同”，但是從實驗結果上看差距還是十分明顯的。因為從實際上看，Array.Sort<T>對於特殊類型有特殊處理，此外LINQ排序會有復制元素的開銷，因此我之前我認為“找不到LINQ排序的性能有優勢的理由”。可惜這句話已經站不住腳了，我們來觀察一下兩種排序方式在實現上的主要區別：
Array.Sort<T>：使用IComparer<T>對象比較兩個元素的大小。
LINQ排序：首先根據keySelector獲得TKey序列，然後在排序時使用IComparer<TKey>比較兩個TKey元素的大小。
那麼，以此您是否可以判斷出以下兩個排序方法的性能高低？
public class Person
{
public int Age { get; set; }
}
public class PersonComparer : IComparer<Person>
{
public int Compare(Person x, Person y)
{
return x.Age - y.Age;
}
}Person[] people = ...
var byLinq = people.OrderBy(p => p.Age).ToList();
var byArray = Array.Sort(people, new PersonComparer());在實際測試之前我無法做出判斷，因為它們其實各有千秋：
Array.Sort<T>：雖然不需要進行額外的元素復制，但是調用PersonComparer.Compare方法的開銷較大——訪問Age屬性相當於調用get_Age方法（如果沒有內聯的話——不過從實際結果看的確被內聯了）。
LINQ排序：雖然需要進行額外的元素復制，而且需要事先計算出排序用的鍵值（Age屬性），但是在排序時只需直接比較int即可，效率較高。
這其實也就是某些測試中發現LINQ排序性能較高的“秘密”。為什麼同樣排序Person序列時，我的測試（http://gist.github.com/282796）表明Array.Sort<T>較快，而其他一些朋友卻得到LINQ排序較快的結果呢？這是因為我的Person類直接使用了公開字段而不是屬性，這樣避免了方法調用的開銷（因為有內聯，這點應該不是問題）。此外，另一些朋友的PersonComparer在比較兩個int時使用了x.Age.CompareTo方法——這又比直接進行int減法要慢上一些了。
那麼，還有影響兩者性能的因素嗎？我們有辦法提高數組排序的性能嗎？畢竟很多時候我們需要直接排序，而不是生成新的序列。下次我們再來討論這些問題吧。
