はじめに

そもそも筆者の下記記事で .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 関数を使ってしまった。インテルアーキテクチャ以外の人には申し訳ない。

ilog2 関数

/* 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]);