はじめに
そもそも筆者の下記記事で .NET Framework の Array.Sort の謎の動作に悩まされたのが発端である。.NET Framework の Array.Sort では差がゼロとなることが分かり切っているにも関わらず，同じ要素同士の比較を行う場合があったのだ。
数万個のファイルの重複チェックを行うプログラムをC#でささっと作る３～.NETのArray.Sortの謎に挑む - Qiita
その後の継続的な調査によって .NET Framework の Array.Sort のアルゴリズムについて把握することができた。
ついに .NET Framework 4.8 の Array.Sort を解明した - Qiita
これで当初の目的を果たし，一連の記事を完結しても良かったのだが，今回の記事は @muedever さんの指摘が発端である。17 個の整数配列の昇順ソートで比較関数の呼び出し回数を比べてみたところ，uCRT の 78 回に対し，.NET Framework 4.8 では 106 回も要したことに対して下記のコメントを受けた。
@muedever 2025-03-31 00:56
.NET9でテストプログラムを試してみたら56回でした
そう，最新の .NET では，ライブラリの中身にかなり手が入れられて効率向上が図られているようなのだ。
先に結論を書く
.NET Core の Array.Sort はいろいろ手を加えられてることが判明した。
- 基本的なクイックソートの部分はかなり改善されている。
- 差分がゼロになっていることが分かっている同値同士の比較は行わない。
- 小型ソートが導入されており，要素数が 16 個以下になると挿入ソートが実行される。
- これ以外にも細かい改善が行われており，計算量が少なくなっている。
- イントロソートが採用されており，再帰関数の呼び出しが深くなるとヒープソートが呼び出される。
- この深さは .NET Framework 4.8 では固定値 32 だったが，.NET Core ではデータ個数の対数に比例するようになっている。
- ヒープソートのアルゴリズムは .NET Framework 4.8 のものと同じ。
結論を一言でまとめると，.NET Core の Array.Sort はクイックソートとしては至高の出来かもしれない。
ソースコード全容
.NET Core の Array.Sort の解読にはとんでもない時間を要したが，同じような動きをするものをC言語で作ることができた。簡単のため int 型のソートに特化した。さすがにちょっと長くはなったが全容を紹介する。とはいっても 100 行以内なので頑張って読める量だとは思う。
/* 001 */ #include <intrin.h>
/* 002 */ typedef int (*COMPARE)(int, int);
/* 003 */ static void swap(int *p, int *q) {
/* 004 */ int temp = *p;
/* 005 */ *p = *q;
/* 006 */ *q = temp;
/* 007 */ }
/* 008 */ static void heap(int *a, int len, int parent, COMPARE compare) {
/* 009 */ int d = a[parent];
/* 010 */ int child;
/* 011 */ while((child = 2 * parent + 1) < len) {
/* 012 */ if(child + 1 < len && compare(a[child], a[child + 1]) < 0)
/* 013 */ child++;
/* 014 */ if(compare(d, a[child]) >= 0) break;
/* 015 */ a[parent] = a[child];
/* 016 */ parent = child;
/* 017 */ }
/* 018 */ a[parent] = d;
/* 019 */ }
/* 020 */ static void hsort(int *a, int len, COMPARE compare) {
/* 021 */ for(int i = len / 2 - 1; i >= 0; i--)
/* 022 */ heap(a, len, i, compare);
/* 023 */ for(int i = len - 1; i > 0; i--) {
/* 024 */ swap(&a[0], &a[i]);
/* 025 */ heap(a, i, 0, compare);
/* 026 */ }
/* 027 */ }
/* 028 */ static void sort(int *a, int top, int end, int depth, COMPARE compare) {
/* 029 */ while(top < end) {
/* 030 */ int n = end - top + 1;
/* 031 */ if(n <= 16) {
/* 032 */ if(n == 1) {
/* 033 */ /* do nothing */
/* 034 */ } else if(n == 2) {
/* 035 */ if(top != end && compare(a[top], a[end]) > 0) swap(&a[top], &a[end]);
/* 036 */ } else if(n == 3) {
/* 037 */ int mid = end - 1;
/* 038 */ if(top != mid && compare(a[top], a[mid]) > 0) swap(&a[top], &a[mid]);
/* 039 */ if(top != end && compare(a[top], a[end]) > 0) swap(&a[top], &a[end]);
/* 040 */ if(mid != end && compare(a[mid], a[end]) > 0) swap(&a[mid], &a[end]);
/* 041 */ } else {
/* 042 */ for(int i = top; i < end; i++) {
/* 043 */ int temp = a[i + 1];
/* 044 */ int j;
/* 045 */ for(j = i; j >= top && compare(temp, a[j]) < 0; j--)
/* 046 */ a[j + 1] = a[j];
/* 047 */ a[j + 1] = temp;
/* 048 */ }
/* 049 */ }
/* 050 */ return;
/* 051 */ }
/* 052 */ if(depth == 0) {
/* 053 */ hsort(&a[top], end - top + 1, compare);
/* 054 */ return;
/* 055 */ }
/* 056 */ depth--;
/* 057 */ int mid = top + (end - top) / 2;
/* 058 */ if(top != mid && compare(a[top], a[mid]) > 0) swap(&a[top], &a[mid]);
/* 059 */ if(top != end && compare(a[top], a[end]) > 0) swap(&a[top], &a[end]);
/* 060 */ if(mid != end && compare(a[mid], a[end]) > 0) swap(&a[mid], &a[end]);
/* 061 */ int pivot = a[mid];
/* 062 */ swap(&a[mid], &a[end - 1]);
/* 063 */ int t = top;
/* 064 */ int e = end - 1;
/* 065 */ while(t < e) {
/* 066 */ while(compare(a[++t], pivot) < 0);
/* 067 */ while(compare(pivot, a[--e]) < 0);
/* 068 */ if(t >= e) break;
/* 069 */ swap(&a[t], &a[e]);
/* 070 */ }
/* 071 */ swap(&a[t], &a[end - 1]);
/* 072 */ sort(a, t + 1, end, depth, compare);
/* 073 */ end = t - 1;
/* 074 */ }
/* 075 */ }
/* 076 */ static int ilog2(int x) {
/* 077 */ return 31 - __lzcnt(x);
/* 078 */ }
/* 079 */ void qsort_net3(int *a, int len, COMPARE compare) {
/* 080 */ if(len < 2) return;
/* 081 */ int depth = 2 * (ilog2(len) + 1);
/* 082 */ sort(a, 0, len - 1, depth, compare);
/* 083 */ }
アルゴリズム解説
それでは細かい部分を紹介する。
1. 対数関数
イントロソートでは再帰関数の呼び出し深さが所定値を超えると，ソートアルゴリズムをクイックソートからヒープソートに切り替える。この所定値はデータ個数の対数に比例するため，底が 2 の Log 関数が必要となる。とはいっても小数点以下は切り捨てて良いので単なるビット演算で済む。
$\text{ilog2}(x) = \lfloor \log_2{x} \rfloor$
さて，C言語でどのようにして実装すれば良いかと悩んだが，悪魔が囁いて intrinsic 関数を使ってしまった。インテルアーキテクチャ以外の人には申し訳ない。
/* 001 */ #include <intrin.h>
/* 077 */ static int ilog2(int x) {
/* 078 */ return 31 - __lzcnt(x);
/* 079 */ }
具体的な例を以下に示す。ilog2 はゼロではない最上位ビットの位置を返せばよい。最右端のビット位置はゼロとするので下記の例では 27 となる。LZCNT 命令は最上位ビットから連続するゼロビットの数を返す。下記の例では 4 となるので，31 から 4 を引けば 27 が得られる。
$x \le 0$ の場合のケアがなされていないので汎用的に使う場合には注意が必要である。
2. ピボット位置の交換
.NET Core における Array.Sort の実装において最も感動した部分である。クイックソートでは領域内のデータを無作為に選んだピボット（下図の mid の位置）と比較して大・小二つのグループに分類する。この際，mid の位置のデータと比較するのは自分自身と比較することになり，無駄な比較である。
-
uCRT では，わざわざ
midの位置の前後でループを分割して同値の比較を避けていた。 - .NET Framework 4.8 では同値の比較も気にせず，単一のループで処理していた。
実際，どちらのほうが処理効率が良いかというと .NET Framework 4.8 のほうであった。比較関数の呼び出しが比較的軽めであること，そして近代のプロセッサであればループ構造をシンプルにしたほうが良いのだと思われる。
これに対し，.NET Core の実装では同値との比較を避けるためにピボット位置 mid のデータを末尾から２番目の位置 end - 1 と交換して避難させ，末尾から３番目の位置 end - 2 から比較を開始するようにしている。この結果，単一ループでありながら同値の比較を避けることができる。
コレ考えた人，天才だと思う。
探索開始位置を比較すると下記のようになる。最初にピボットを選択した時点で a[top] <= a[mid] かつ a[mid] <= a[end] であるので，top と end を探索範囲に含める必要はない。そのため .NET Framework の実装は uCRT のものより後退していたのだが，.NET Core になって一気に挽回した印象である。
| 先頭 | 末尾 | |
|---|---|---|
| uCRT | top + 1 |
end - 1 |
| .NET Framework 3.5 | top |
end |
| .NET Framework 4.8 | top |
end |
| .NET Core | top + 1 |
end - 2 |
3. 三分割
クイックソートではピボットの値と比較して大・小二つのグループに分ける。素直な実装では２つに分けたグループそれぞれに対してクイックソートを行う。
uCRT の場合，ピボットの位置 mid から連続してピボットの値と同値の領域はソート済みとして，それら二つの領域に含めない。つまり，領域を３つに分割しているとも言える。
.NET Core の場合，ピボットの値は最後から２番目の位置 end - 1 に退避しているので，それを t の位置と交換する。ここでピボットの値を元の位置に戻すという訳ではないことに注意する。ピボットの値以上の値が連続する領域 [t, end] の中で最も先頭にある場所が t であるから，t の位置の値をピボットの値と交換した後，次のソート範囲に t の位置を含めなくても問題ない。こうして領域を [top, t - 1] と [t, t] と [t + 1, end] の３つに分割し，中央の [t, t] の範囲を次のソート範囲から外すことで次にソートする範囲を少しでも減らしているのだ。
「三分割」とは筆者が便宜上使っている造語である。
4. 挿入ソート
uCRT では領域のサイズが 8 個以下になると，選択ソートに切り替えていた。.NET Framework ではこのような小型ソートは実装されていなかったが，.NET Core では領域のサイズが 16 個以下になると挿入ソートに切り替えるようになった。
/* 042 */ for(int i = top; i < end; i++) {
/* 043 */ int temp = a[i + 1];
/* 044 */ int j;
/* 045 */ for(j = i; j >= top && compare(temp, a[j]) < 0; j--)
/* 046 */ a[j + 1] = a[j];
/* 047 */ a[j + 1] = temp;
/* 048 */ }
選択ソートと挿入ソートの優劣比較については別の記事で取り上げたい。
「小型ソート」も筆者が便宜上使っている造語である。uCRT のソースコード内のコメントには short sort とある。
比較・転送回数の比較
比較・転送回数の比較を示す。試験条件は下記の通りである。
- 200,000,000 個の 32bit 整数を昇順ソートする。
- データの順序は以下の四種類である。
- ゼロ（すべて同値）
- 昇順：0 → 199,999,999
- 降順：199,999,999 → 0
- 乱数：0～199,999,999 の範囲で一様乱数（重複あり）
- 乱数発生器は XorShift である。
| 順序 | uCRT | .NET | .NET2 | .NET3 |
|---|---|---|---|---|
| ゼロ | 399,999,999 | 5,675,718,141 | 5,675,718,141 | 4,977,882,130 |
| 昇順 | 5,363,792,412 | 5,730,237,980 | 5,730,237,980 | 4,983,222,808 |
| 降順 | 5,363,792,412 | 5,730,238,009 | 5,730,238,009 | 9,381,897,621 |
| 乱数 | 6,400,427,154 | 6,916,900,788 | 6,804,184,853 | 6,213,723,201 |
| 順序 | uCRT | .NET | .NET2 | .NET3 |
|---|---|---|---|---|
| ゼロ | 0 | 5,208,609,280 | 5,208,609,280 | 4,961,104,915 |
| 昇順 | 265,782,274 | 0 | 0 | 233,554,429 |
| 降順 | 465,782,278 | 200,000,004 | 200,000,004 | 734,217,525 |
| 乱数 | 2,736,238,624 | 2,770,781,196 | 2,998,522,286 | 2,969,967,591 |
こういうのはグラフにすると一目瞭然である。降順を除けば，.NET3 (.NET Core) の比較回数は少なくなっており，パフォーマンス向上が期待できる。なお，降順のときに比較回数が増えてしまったのは（おそらく）挿入ソートの影響だと考えている。挿入ソートは降順に対しては少し効率が悪くなるものと考えられる。
■ uCRT，■ .NET，■ .NET2，■ .NET3
実行時間の比較
試験条件を以下に示す。
- Cコンパイラは下記の三種類とし，かつターゲットを 32bit (x86) と 64bit (x64) の二種類の組み合わせで合計六種類とする。
- Microsoft Visual C++ 2022
- LLVM clang 17.0.3
- intel C++ compiler：oneAPI 2024.2, Compiler Release 2024.2.1
- 評価マシンのスペックは下記の通り
- Windows10 2022H2，Core i7-13700 5.1GHZ，32GB
試験結果を以下に示す。単位は秒である。
| コンパイラ | 順序 | uCRT | .NET | .NET2 | .NET3 |
|---|---|---|---|---|---|
| Visual C++ 32bit版 |
ゼロ | 0.090 | 1.891 | 1.838 | 1.341 |
| 昇順 | 1.433 | 1.262 | 1.351 | 1.173 | |
| 降順 | 1.475 | 1.275 | 1.369 | 2.046 | |
| 乱数 | 15.505 | 14.986 | 15.301 | 12.873 | |
| Visual C++ 64bit版 |
ゼロ | 0.093 | 2.187 | 2.162 | 1.383 |
| 昇順 | 1.582 | 1.589 | 1.567 | 1.057 | |
| 降順 | 1.617 | 1.607 | 1.576 | 1.822 | |
| 乱数 | 15.500 | 15.562 | 14.913 | 12.431 | |
| LLVM clang-cl 32bit版 |
ゼロ | 0.098 | 2.129 | 2.160 | 1.182 |
| 昇順 | 1.627 | 1.425 | 1.460 | 0.901 | |
| 降順 | 1.688 | 1.461 | 1.509 | 1.592 | |
| 乱数 | 15.636 | 14.389 | 14.998 | 11.987 | |
| LLVM clang-cl 64bit版 |
ゼロ | 0.089 | 2.334 | 2.290 | 1.324 |
| 昇順 | 1.460 | 1.338 | 1.357 | 0.897 | |
| 降順 | 1.523 | 1.381 | 1.394 | 1.574 | |
| 乱数 | 15.710 | 14.703 | 14.780 | 12.694 | |
| intel icx-cl 32bit版 |
ゼロ | 0.070 | 2.255 | 2.136 | 1.230 |
| 昇順 | 1.592 | 1.435 | 1.282 | 0.924 | |
| 降順 | 1.691 | 1.464 | 1.309 | 1.611 | |
| 乱数 | 17.120 | 14.694 | 14.686 | 12.391 | |
| intel icx-cl 64bit版 |
ゼロ | 0.064 | 2.388 | 2.310 | 1.899 |
| 昇順 | 1.366 | 1.536 | 1.583 | 1.223 | |
| 降順 | 1.491 | 1.580 | 1.623 | 2.153 | |
| 乱数 | 16.584 | 15.106 | 15.053 | 13.433 |
グラフにすると分かり易い。乱数の場合，すべてのコンパイラにおいて .NET3 (.NET Core) が最優秀であるという喜ばしい結果となった。降順の場合，比較回数ではかなり増加したので心配したが，計算時間としては（もともと少ないこともあって）大したレベルではないことが分かって安心した。
■ uCRT，■ .NET，■ .NET2，■ .NET3
クイックソートキラーへの耐性
クイックソートキラーへの耐性も確かめてみよう。ベンチ用のコードは前回の記事と共通しているので省略する。
.NET3 (.NET Core) は，ヒープソートに切り替わらない小サイズの領域では圧倒的に比較回数が少ないことが分かる。
| 要素数 | uCRT | .NET | .NET2 | .NET3 |
|---|---|---|---|---|
| 10 | 39 | 65 | 65 | 13 |
| 20 | 124 | 195 | 195 | 64 |
| 50 | 679 | 885 | 885 | 650 |
| 100 | 2,604 | 3,035 | 2,769 | 1,867 |
| 200 | 10,204 | 11,085 | 7,137 | 4,837 |
| 500 | 63,004 | 65,235 | 21,266 | 15,155 |
| 1,000 | 251,004 | 255,485 | 46,197 | 34,960 |
| 2,000 | 1,002,004 | 1,010,985 | 97,951 | 78,647 |
| 5,000 | 6,255,004 | 6,277,485 | 261,268 | 231,444 |
| 10,000 | 25,010,004 | 25,054,985 | 544,536 | 505,168 |
| 20,000 | 100,020,004 | 100,109,985 | 1,130,597 | 1,090,906 |
| 50,000 | 625,050,004 | 625,274,985 | 2,960,700 | 2,960,448 |
| 100,000 | 2,500,100,004 | 2,500,549,985 | 6,125,482 | 6,326,338 |
| 200,000 | 10,000,200,004 | 10,001,099,985 | 12,661,996 | 13,466,784 |
| 500,000 | 62,500,500,004 | 62,502,749,985 | 32,968,189 | 35,977,618 |
| 1,000,000 | 250,001,000,004 | 250,005,499,985 | 67,979,733 | 75,964,727 |
こういうのは両対数グラフにすると分かり易い。.NET3 (.NET Core) も .NET2 (.NET Framework 4.8) と同様，途中でヒープソートに切り替わって傾きが緩やかになり，$O(n \log n)$ になっていることが分かる。また，その変化点も .NET2 より早いことが分かる。
■ uCRT，■ .NET，■ .NET2，■ .NET3
結論
以上より，.NET Core の Array.Sort で採用されたクイックソート実装は，少なくとも自分が見たコードの中では至高の出来栄えであったと言える。
同じマイクロソフト製の uCRT のほうは進化が止まっているのに対し，.NET は .NET Framework 3.5 から .NET Framework 4.8，そして .NET Core へと継続的に進化しているのも素晴らしい。
なお GNU C Library の qsort はマージソートになっていて直接比較できない。
おそらく，これらを超える可能性があるのは C++ くらいだろう。
備考
本コードの 58～60 行目を再掲する。もともと同値との比較を避けるために下記のコードになっていた。
/* 058 */ if(top != mid && compare(a[top], a[mid]) > 0) swap(&a[top], &a[mid]);
/* 059 */ if(top != end && compare(a[top], a[end]) > 0) swap(&a[top], &a[end]);
/* 060 */ if(mid != end && compare(a[mid], a[end]) > 0) swap(&a[mid], &a[end]);
しかし，本ソートでは小型ソートが採用され，top と end が 16 以上離れていることが保証されている。すなわち top と end，そして mid = top + (end - top) / 2 の全て，互いに一致しないことが保証されているので下記のように比較を簡略化してもよい。
/* 058 */ if(compare(a[top], a[mid]) > 0) swap(&a[top], &a[mid]);
/* 059 */ if(compare(a[top], a[end]) > 0) swap(&a[top], &a[end]);
/* 060 */ if(compare(a[mid], a[end]) > 0) swap(&a[mid], &a[end]);