OrderByとThenBy - IOrderedEnumerableの仕組み

LINQには要素を並び替えるOrderByと、OrderByで同じ大きさだった要素をその中でさらに並び替えるThenByという拡張メソッドが用意されています。

var files = Directory.GetFiles(@"（中略）\OrderByTest")
    .Select(p => new FileInfo(p))
    .OrderBy(p => p.Extension.ToLower())
    .ThenByDescending(p => p.Name);

foreach(var file in files)
    Console.WriteLine(file.Name);    

例えばソースコードのフォルダに対してこんなコードを実行してみました。
まずは拡張子に対して昇順でソートをかけ、拡張子が同じものについては降順でファイル名にソートをかけています。

 確かに拡張子は昇順（config→cs→csproj）ですが、ファイル名は降順（Program→Enumerable）になっています。

ちょっと考えれば、ThenByが無くてもファイル名で降順にソートしてから拡張子で昇順にソートすれば（安定なソートである前提で）同じ結果が得られることがわかります。まあ、2回ソートをすることになりますが。

ですが、OrderBy().ThenBy()という書き方は「まずソートして、同じだったらさらに条件を追加して」となり流れが非常にわかりやすいです。また、詳しくは後述しますが、このやり方ではソートは1回しか行われておらず、上記の2回ソートする方法に比べれば効率が良いです。

さて、どうなっているか仕組みを見てみましょう。

IOrderedEnumerable<T>

当然ですが、ThenBy()はソートされたシーケンスにしか適用できません。すなわち、IEnumerable<T>に対する拡張メソッドではないのです。OrderBy()やThenBy()はIOrderedEnumerable<T>を返し、これに対する拡張メソッドとしてThenBy()が定義されています。

IOrderedEnumerable<T>はIEnumerable<T>とIEnumerableを継承しており、
IOrderedEnumerable<T>としてはCreateOrderedEnumerable()メソッドが追加されています。

IOrderedEnumerable<TElement> CreateOrderedEnumerable<TKey>(
    Func<TElement, TKey> keySelector,
    IComparer<TKey> comparer,
    bool descending
)

最初このメソッドを見たときは「なんやねんこれ」と思いました。何をやるメソッドかまるでわからない、悪いネーミングのメソッドです。

実はこれ、単にThenBy()が自分が渡されたパラメーターを渡しているだけなのです。
ソースコードを見れば一目瞭然です。

public static IOrderedEnumerable<TSource> ThenBy<TSource, TKey>(this IOrderedEnumerable<TSource> source, Func<TSource, TKey> keySelector) {
    if (source == null) throw Error.ArgumentNull("source");
    return source.CreateOrderedEnumerable<TKey>(keySelector, null, false);
}

すなわちこれがThenByの実体なわけですね。第1引数はキーを返すデリゲート、第2引数はキーの比較クラス、3つ目の引数は昇順降順を指定するbooleanです。
ThenBy()メソッドは第1引数にOrderByなどが返したIOrderedEnumerableを受け取りますから、この実体に対してCreateOrderedEnumerableを呼び出してThenByの動作を規定するわけです。

IOrderedEnumerableの実体は、LINQの場合はOrderedEnumerableクラスが担っています。このクラスはinternalなのでライブラリ外からは見えません。
上記のソースコードを追っていくとわかりますが、OrderedEnumerable.CreateOrderedEnumerableは自身を親条件に持つOrderedEnumerableを返します。そして、実際に列挙されはじめたとき（GetEnumeratorが呼び出されたとき）にクイックソートを用いてソートを行いますが、そのソート時の比較で親条件から順に適用していき、比較結果が"等価"になったときに再帰的に子条件を用いることでThenByを実現しています。

internal override int CompareKeys(int index1, int index2) {
    int c = comparer.Compare(keys[index1], keys[index2]);
    if (c == 0) {
        if (next == null) return index1 - index2;
        return next.CompareKeys(index1, index2);
    }
    return descending ? -c : c;
}

（ソースコードはこちら）


余談ですが、クイックソートは比較ソートの中では最も速い（ソート時間の期待値が最も小さい）と言われていますが、安定なソートではありません。そこで、この比較メソッドで、値が等価ならインデックスの大小関係を返すことで安定なソートを実現しているようです。

まとめ

• OrderBy()やThenBy()はIEnumerable<T>を継承したIOrderedEnumerable<T>を返す
• IOrderedEnumerable<T>.CreateOrderedEnumerable()はThenByの条件を追加したIOrderedEnumerable<T>を返す
• IOrderedEnumerable<T>のLINQ実装であるOrderedEnumerableクラスはクイックソートを行い、その比較時に最も親の条件から順に適用してThenByを実現している （すなわちソートは1回のみ）

ということで、もしも俺の考えた最強のソートアルゴリズムをLINQで使いたかったら、IOrderedEnumerable<T>を実装した（CreateOrderedEnumerable()を実装した）クラスを返すことで、自動的にThenByも定義できてしまうということになります。

まあ、比較ソートの中では最速のクイックソートをがOrderByに使われている以上、OrderByを改善したくなることはまず無いとは思いますけどね。意図的に最悪なピボットを選ばせるようなシーケンスを与えない限り、マージソートのほうが良いなんていうことは無いでしょう（ちなみにシーケンスの中央の値をピボットとするアルゴリズムを採用しているようなので、ソート済みシーケンスに対してOrderByを呼び出しても$O(n^2)$にはならないようです。