ソートアルゴリズムの限界 - 比較ソートと非比較ソート

ソートアルゴリズムはアルゴリズムの初歩で勉強することだと思います。
最悪計算時間、平均計算時間や安定なソート、不安定なソートなんかの話が出てきますよね。簡単なアルゴリズムの例としてバブルソートや選択ソート、挿入ソートなどが出てきて、そのあとに高速なアルゴリズムとしてクイックソートやマージソートが出てくると思います。

さて、それではソートのスピードに限界はあるのでしょうか。

計算時間の"オーダー"

その前に復習です。よく「計算時間のオーダー」というものが言われますね。話を厳密にするために定義しておきましょう。

ビッグオー記法

定義：ある関数$f(n)$に対して定数$a$,$c$が存在し、すべての$n>a$に対して$f(n) \leq c \cdot g(n)$を満たすとき、$f(n)=O(g(n))$と書く。

これがいわゆるオーダーと呼ばれるものです。どんな$a$を取ってきても、それより大きな$n$だったら必ず$f(n)$は$g(n)$の定数倍より小さくなる、ということを言っています。$n$が無限まで行っても必ず$g(n)$の定数倍にはかなわないため、最も大きくなるパターンを想定するうえで非常に有用です。

ビッグオメガ記法

定義：ある関数$f(n)$に対して定数$a$,$c$が存在し、すべての$n>a$に対して$f(n) \geq c \cdot g(n)$を満たすとき、$f(n)= \Omega (g(n))$と書く。

オーダーよりもちょっとマイナーな記法だと思います。ビッグオー記法との違いは不等号です。どんな$a$を取ってきても、それより大きな$n$だったら必ず$f(n)$は$g(n)$の定数倍より大きくなる、ということを言っています。こちらは逆に最も小さくなるパターンを想定する上で有用です。


これらの定義は一般化して数学的に厳密に行ったものです。アルゴリズムの良さの尺度として用いるときは、$n$はたいてい配列長とします。配列長が長くなるとソートにかかる時間$f(n)$がどうなるのか、というのが最も評価すべき指標だからです。
細かな話をすればそれ以外の評価指標もあるのですが、まずはここから入ります。

注意事項

1. 定数倍までは気にしない

これらの指標は定数倍の違いは許容しています。これは、あくまでも$n$に対する相関を考えているためです。ですので、同じオーダーでも計算時間が平気で2倍3倍、極端な話10倍100倍違うこともあり得ます。
そんなの困るじゃないかと思うかもしれませんが、逆に言えば、オーダーが同じアルゴリズムでは$n$がどんなに増えても高々定数倍しか計算時間は変わらないということになります。オーダーが変わると定数倍よりも大きな計算時間の差が出るため、それに比べれば高々定数倍しか差が出ないのは、アルゴリズムの良し悪しを検討する上では些細な問題なのです。逆に言えば、その些細な問題を気にするようなステージでは、この記事の議論は的外れであるという認識を持っていただいて構いません。

2. タイトな表現をすること

上記の定義に従えば、例えば$O(n^2)$のところを$O(n^{100})$と書いても間違いではありません。ですが、評価指標としては役に立たないものになってしまいます。ですので、特別な要求が無い限りは最もタイトな表現をすることとします。
タイトな表現とは、あるアルゴリズムについて$O(f(n))$と$O(g(n))$という2通りの書き方があったとき、$f(n)=O(g(n))$かつ$g(n) \neq O(f(n))$であるとき、$f(n)$のほうがよりタイトな表現と定義することができます。

比較ソートの理論限界

さて、種々の定義が終わったところで本題に移っていきます。
クイックソートとマージソートは高速で、平均計算時間は$O(n \log n)$だという認識を持っている人は多いと思います。
ではソートはこれ以上速くなることができるのでしょうか。

実は、大小比較に基づいたソートには理論限界があります。

比較とは、配列の中の2つの要素$a$,$b$を取り出して、$a \leq b$か$a>b$かを判定する作業のことを言います。
比較を1回行うと、「以上」か「未満」の2通りの答えが出てくるため、内容によって配列の並べ方が2通りに分岐します。そこからもう1回比較をするとさらに2通りに分岐するため、$t$回の比較では$2^t$種類の並べ方に分類することができます。
一方、ソートとはいくつもある並び替え方の中から唯一の並び方を決定する作業だと言いかえることができます。$n$個の要素の並び替え方は$n!$通りありますので、以下の式が成り立ちます。 $$2^t \geq n!$$ いくつもある並べ方の中から1つの並べ方を特定するには、すべての並べ方をカバーできるだけの比較はしておかなければなりません。逆に言えば（と言うよりか対偶に言えば）、すべての並べ方をカバーできない回数の比較では、1つの並べ方を特定することができません。なのでこの式が成り立つわけです。

ここからの式変形はスターリングの公式を使うとした文献が多いですが、実はそんなに大した計算ではないので自力で解いてみましょう。 $$\begin{align*} 2^t &\geq n!\\ t &\geq \log n!\\ &\geq \sum_{k=1}^{n} \log k > \int_1^{n} \log x \mathrm{d}x \end{align*}$$ 最後の不等式は面積を考えれば一発ですね。

$$\begin{align*} \int \log x \mathrm{d}x &= x \log x - \log e \int x \cdot \frac{1}{x}\mathrm{d}x\\ &= x \log x - x \log e+C \end{align*}$$ $$\therefore t>n \log n+(1- n) \log e =O(n \log n)$$ logの積分とか懐かしいですね。ただ、logは底が2なので積分時には注意する必要があります。
これによって、比較に基づいたソートである限り、最悪計算時間は$\Omega (n \log n)$であることがわかりました。クイックソートやマージソートは、オーダーの上では理論上最速なのです。

比較に基づかないソート

さて、前節でわざわざ比較に基づいたソートと書いたからには、比較に基づかないソートも存在するわけです。そうすれば、$O(n \log n)$を割り込むかもしれません。

バケットソート

配列は任意の要素を$O(1)$の計算時間で読み書きできます。ですので、並び替えたい数列の要素が0以上の整数で上限がわかっている場合、0～上限までの長さの配列を用意することで数列に含まれるすべての整数の個数を$O(n)$で数えきることができます。すべての個数がわかれば、小さいほうから順にその整数をその個数入れていけばソートの完成です。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

const int max = 10; Random rnd = new Random(); int[] array = new int[100];   //乱数を準備（値は0～9） for(int i = 0; i < array.Length; i++)     array[i] = rnd.Next(10);   Console.WriteLine("Before:"); Console.WriteLine(string.Join(", ", array));   //バケットソート int[] result = new int[max]; for(int i = 0; i < array.Length; i++)     result[array[i]]++; //個数をカウントする   int pos = 0; for(int i = 0; i < max; i++) {     for(int j = 0; j < result[i]; j++)         array[pos++] = i;    //個数分だけその数を入れる }   Console.WriteLine("After:"); Console.WriteLine(string.Join(", ", array));

途中で2段ループを回しているように見えますが、これは2段分合計でarray長しか繰り返さないので、$O(n)$になります。$O(n)$でソートが終わるとても高速なソートになります。

ただ、これの欠点は0以上の整数にしか使えないことで、さらに0～上限までのメモリが必要になります。上のサンプルコードでは上限を9としたので大したことありませんが、例えば32bit整数だったら4GiBのメモリが必要になってきます。実用上かなり不便です。

鳩ノ巣ソート

上記のバケットソートは数字の数を数えているだけですので、数字以外のソートには使えません。数字を付帯する何かしらのデータ（例えばファイルサイズを持っているファイル情報データ）をソートしたい場合に一工夫必要です。
そこで、ソートしたい整数に対応した配列の各要素として今度はこのデータを収める配列をそれぞれ確保すればバケットソートを適用できます。これを鳩ノ巣ソートと呼びます。

この時、必要なメモリは、並び替えたい整数の種類$k$と配列長$n$を使って$kn$と表せます。例えば32bit数値のデータ1024個を並び替えたければ4TiBのメモリが必要になります。もはやアホくさいレベルです。
（並び替えるデータを片方向連結リストとすることでバケットソートレベルまで使用するメモリを減らせます。が、まだまだ非現実なレベルです。）

基数ソート

バケットソートや鳩ノ巣ソートではとてつもない大きさのメモリが必要になるので、その作業を何回かに分けてメモリの使用量を抑えたのが基数ソートになります。
まず1の位だけを見て鳩ノ巣ソートを行います。この時、10進数ならば取り得る数字は10種類だけなのでメモリ量も配列長の10倍ほどで済みます。
次は、並び替え終わったデータに対して今度は10の位で鳩ノ巣ソートを行います。安定なソート前提だと、10の位がソートされ、同じ10の位については1の位がソートされた状態になります。すなわち下2桁がソートし終わったことになります。
次は100の位、1000の位と同様の処理をしていきます。最大桁数まで処理を終えたら終了です。

コンピューターは通常8bit単位でデータを扱いますので、256進数とみなして基数ソートを行えば、例えば32bit値ならば4回のループで計算が終わります。鳩ノ巣ソートと同様、片方向連結リストを使うことでメモリの使用量もそこそこ抑えることができます。

スリープソート

いつもネタ枠扱いされていますが、これも立派な非比較ソートです。

並び替えたい配列の各要素に対して、例えばその数×1ミリ秒待つタイマーを一斉にスタートさせ、タイマーが鳴ったものから順に結果を格納していけばソートが完了するというものです。
バケットソート、鳩ノ巣ソート、基数ソートは整数しかソートできませんでしたが、時間は配列と違って連続ですので、スリープソートは小数に対しても行うことができます。すごい！！

ただ、これを現代の一般的なコンピューターにやらせようとすると、実際は中には1つのストップウォッチのみが入っていて、タイマー時間をもとに数字を並び替えて、小さいほうから順に鳴らしていくということになってしまいます。スリープソートをしたつもりで裏でOSが別の手法でこっそりソートをしているんですね。
また、「一斉にタイマーをスタートさせる」というのも一般的なコンピューターでは現実的に難しく、 スタートのタイミングの誤差だったり、もしくはスレッド切替時の誤差で正確なソートができなくなってしまうこともあります。

そういった点からいつもネタ扱いされていますが、私個人としては、バケットソートをメモリ空間軸上から時間軸上に動かして考案された、なかなか面白いアイディアだと思っています。
現実を見ていないソートアルゴリズムなのではない、現実が追い付いていないだけなのだ。

計算時間の比較

実際にマージソートと基数ソートを実装し、計算時間を比較してみました。
お約束ですが、実装や環境で速度そのものについては変わってくると思います。ただ、オーダーについての考え方は同じはずですので、その着眼点で見てください。

まずは単純な比較です。
マージソートの$O(n \log n)$の見た目が$O(n)$とほとんど変わらないのでパッと見ではわかりませんが、近似直線を引くと確かに直線より上側に沿っている（2階微分が正）のがわかります。
一方で基数ソートのほうは近似直線に沿っています。確かに$O(n)$です。

おまけですが、これの原点付近を拡大するとこうなります。

配列長が200前後でマージソートと基数ソートの計算時間が逆転しています。

これがオーダーの威力です。配列長が小さいと実装の差が出てきますが、配列長が大きくなるとオーダーが圧倒的な支配力を持ってきます。ですので、まずはオーダーの小さなソート手法を確立するのが先決なのです。

仮想ネットワークドライバ「TAP-Windows」をC#から操作する - Tap.NET 0.1.0

ネットワークの勉強をしていると、イーサネットパケットレベルで他のコンピューターとやり取りをしてみたくなることがあります。パソコンを2台起動して、リモートデスクトップを使いながらいろいろ実験するのも悪くないですが、1台ですべて完結できたら便利ですよね。Wiresharkでキャプチャしたパケットを自身のPCに送り直すくらいのことなら、仮想ネットワークドライバをインストールして、ソフトウェア的にエミュレートすることもできるはずです。

ググっていると、OpenVPNに付属している仮想ネットワークドライバ「TAP-Windows」というものを見つけました。本来はVPNで使用するための仮想ネットワークドライバのようですが、Win32APIを介してパケットのやり取りができるようです。

というわけで、この.NETラッパーを作ってC#等から使えるようにしてみました。

1. TAP-Windowsのインストール

まずはTAP-Windowsをインストールしなければ始まりません。

Download - OpenVPN.net

この中からOpenVPNのWindows用インストーラをダウンロードしインストールをします。OpenVPN本体自体は不要ですので、インストールにて他のチェックボックスは極力外しておきましょう。

インストールが終わったらネットワークと共有センターを開いてちゃんとインストールできているか確認しておきましょう。名前をわかりやすいものに変更しておくといいかもしれません。

余談ですが、Wiresharkがパケットキャプチャで使っているWinPcapサービスは起動時に存在するネットワークアダプタをスキャンしているようです。なので、WinPcapからTAP-Windowsを見るためには一旦パソコンを再起動する必要があります。

2. ラッパーを作る

TAP-WindowsにアクセスするにはWin32APIのCreateFileやReadFile、WriteFile関数などを呼び出します。概ねファイルの読み書きと同様にできると言っていいでしょう。
C#からP/Invokeで頑張るのもありかもしれませんが、だんだんわけがわからなくなってきたり、結局定数の中身を除くために延々とwindows.hを辿ったり、unsafeを強要されそうになってしまったり…というお約束のルートが見えています。ですので、プログラミング界の黒魔術(※)と呼ばれているC++/CLIでラッパーを作ります。あまり深入りはし過ぎないように、ほどほどの作りこみにしておきましょう。
※私が勝手に呼んでいるだけです。
 

コンストラクタ

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

/// <summary> /// コンストラクタ /// </summary> /// <param name="guid">TAPデバイスのGUID</param> TapDotNet::Tap::Tap(String ^ guid) {     String^ path = "\\\\.\\Global\\" + guid + ".tap";     pin_ptr<const wchar_t> pszPath = PtrToStringChars(path);       ULONG status = TRUE;     DWORD dwLen;         //TAPデバイスを開く     hTap = CreateFileW(pszPath, GENERIC_READ | GENERIC_WRITE, 0, 0, OPEN_EXISTING, FILE_ATTRIBUTE_SYSTEM, 0);       if(hTap == INVALID_HANDLE_VALUE)         throw gcnew InvalidOperationException("Cannot open the device");       //TAPデバイスをアクティブに     status = TRUE;     if(!DeviceIoControl(hTap, CTL_CODE(FILE_DEVICE_UNKNOWN, 6, METHOD_BUFFERED, FILE_ANY_ACCESS), &status, sizeof(status), &status, sizeof(status), &dwLen, NULL)) {         CloseHandle(hTap);         hTap = NULL;         throw gcnew InvalidOperationException("Cannot activate device");     } }

まずはデバイスの初期化をします。
CreateFileのファイル名を指定するパラメーターには"\\.\Global\{GUID}.tap"を渡します。GUIDの取得方法はまた後程。その他のパラメーターはなんとなくわかると思います。
デバイスを開いたら次はDeviceIoControl関数を呼び出してデバイスをアクティブにします。この時点でWindowsはネットワークケーブルが差し込まれたと認識します。

パケット送信

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

/// <summary> /// データを送信するメソッド /// </summary> /// <param name="data">パケット</param> void TapDotNet::Tap::SendData(array<Byte>^ data) {     if(data == nullptr) throw gcnew ArgumentNullException("data");     if(hTap == NULL) throw gcnew ObjectDisposedException("Tap");       pin_ptr<Byte> pinned = &data[0];     DWORD dwWritten;       if(!WriteFile(hTap, pinned, data->Length * sizeof(Byte), &dwWritten, NULL))         throw gcnew InvalidOperationException("WriteFile Error: " + GetLastError().ToString()); }

データの送信にはWriteFile関数を使います。書き込んだバイトを取得するパラメーターは必要無くてもNULLにしてはいけないようです。Windows10では動きましたがWindows7ではAccessViolationExceptionを吐いて動かず、しばらくハマってしまいました（ドキュメンテーションにもOverlapped構造体とともにNULLにはできないと書いてありました…）。

パケット受信

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39

void TapDotNet::Tap::StartWatching() {     if(!ReceiveWatching) {         WatcherThread = gcnew Thread(gcnew ThreadStart(this, &TapDotNet::Tap::WatchReceive));         WatcherThread->Start();     } }   void TapDotNet::Tap::StopWatching() {     if(ReceiveWatching) {         WatcherThread->Abort();         WatcherThread->Join();         WatcherThread = nullptr;     } }   void TapDotNet::Tap::WatchReceive() {     try {         UCHAR Buf[1518] = { 0 };         DWORD dwLen = 0;           while(true) {             if(ReadFile(hTap, Buf, sizeof(Buf), &dwLen, NULL))                 if(Filter(Buf, dwLen))                     RaiseReceiveEvent(Buf, dwLen);             else {                 DWORD lasterr = GetLastError();                 if(lasterr != 0) {                     RaiseErrorEvent("ReadFile Error", lasterr);                     break;                 }             }                    }     }     catch(ThreadAbortException^) {     } }

データの受信は受信用スレッドを作って行います。
えっ、今の時代Thread直作りは流行らないって？C++/CLI自体が流行らないので許してください…。

Filter関数は受信したパケットにフィルターを掛けるものです。全てのパケットをイベントでRaiseしていてはイベントの嵐になってしまいますので、そういうのはできるだけ根っこで止めるということで、受信直後にフィルターを掛ける機能を実装しました。
ただ、ここで受信するのはイーサネットフレームで、そのヘッダで得られる情報は発信元と宛先のMACアドレスと、IPv4などのネットワーク層水準のプロトコルの種類くらいです。
トランスポート層のプロトコル種類（TCPとかUDPとか）やIPアドレスなどを判別する機能も付けたいところではありますが、じゃあ同じようにAppleTalkのフィルターも作るのかと言ったらそんなの作る気にもなれず、ひとまずそのレベルのフィルターでとどめておくことにしました。
C++/CLIですからね。深入りは厳禁です。

デストラクタ/ファイナライザ

1 2 3 4 5 6 7 8 9 10 11 12 13

TapDotNet::Tap::~Tap() {     StopWatching();     this->!Tap(); }   TapDotNet::Tap::!Tap() {     if(hTap != NULL) {         CloseHandle(hTap);         hTap = NULL;     } }

最後は終了処理をします。C++/CLIではDisposeパターンが自動的に実装されるらしく、C#でのディスポーザはC++/CLIではデストラクタとして実装するそうです。
マネージドリソース（今回はThread）はデストラクタ、アンマネージドリソース（CreateFileのハンドル）はファイナライザにて解放処理を行います。

3. 実際に使う

やっとC++/CLIの呪縛から逃れました。
前述のTAP-WindowsのGUIDを求める方法は超簡単です。NetworkInterfaceクラスのIdプロパティがそれに相当します。ですのでこのようなプログラムでどうでしょうか。

1 2 3 4 5 6 7 8 9

var tapnic = NetworkInterface.GetAllNetworkInterfaces().SingleOrDefault(p => p.Description == "TAP-Windows Adapter V9");   using(var tap = new Tap(tapnic.Id)) {     tap.DataReceived += Tap_DataReceived;     tap.ReceiveWatching = true;     Task.Delay(TimeSpan.FromSeconds(10)).Wait();     tap.ReceiveWatching = false;     tap.DataReceived -= Tap_DataReceived; }

バージョン違い等でDescriptionが書き換わったらこれではうまく動かなくなってしまいますが…となるとユーザーに選択させるとかですかね。まあ、サンプルコードとしては十分でしょう。
また、これはコンソールアプリケーションで作ったので、Task.Delay().Wait();ができますが、GUIアプリケーションに移植する際は気を付けてください。あくまでもTaskはasync/awaitすべきです。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29

private static void Tap_DataReceived(object sender, DataReceivedEventArgs e) {     Console.WriteLine($"======== {e.Data.Length} bytes ========");       const int linecnt = 16;     const int separatedcnt = 8;       foreach(var (list, index) in e.Data.Buffer(linecnt).Select((list, index) => (list, index))) {         var line = new StringBuilder();           line.Append($"{index * linecnt:X4}  ");         line.Append(string.Join("  ", list             .Select(p => p.ToString("X2"))             .Concat(Enumerable.Repeat("  ", linecnt - list.Count))             .Buffer(separatedcnt)             .Select(p => string.Join(" ", p))));         line.Append("  ");         line.Append(string.Join(" ", list             .Select(p => (char)p)             .Select(p=>char.IsControl(p) ? '.' : p)             .Concat(Enumerable.Repeat(' ', linecnt - list.Count))             .Buffer(separatedcnt)             .Select(p => new string(p.ToArray()))));           Console.WriteLine(line);     }       Console.WriteLine(); }

データを受信したときにカッコよくダンプするコードを書きました。
ValueTupleとIxのBuffer()を使っているので、相応のC#バージョンと参照が必要です。

送信は超簡単です。

1 2 3

using(var tap = new Tap(tapnic.Id)) {     tap.SendData(ping); }

pingはpingのイーサネットフレームのバイト列です。Wiresharkの下のほうに見えるアレです。

Tap.NETから送ったpingパケットをWiresharkで無事拾えました。

4. ダウンロード

例によってNugetに置いておきました。現時点ではひとまずプレリリース扱いにしております。

Tap.NET 0.1.0-beta1

OrderByとThenBy - IOrderedEnumerableの仕組み

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

1 2 3 4 5 6 7

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()メソッドが追加されています。

1 2 3 4 5

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

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

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

1 2 3 4

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を実現しています。

1 2 3 4 5 6 7 8

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)$にはならないようです。