.NET (Framework) のArray.Sortのアルゴリズムを探る

# はじめに

これまでソート関数について勉強してきた。

- [uCRT の qsort のソースを読む - Qiita](https://qiita.com/TETSURO1999/items/ff12ba697a1ae79cbf9f)
- [GNU C Libraryのqsortはクイックソートではないの？ - Qiita](https://qiita.com/TETSURO1999/items/3eff3b6a5e3983630f3c)
- [最強コンパイラを使えばマージソートは遅くない？ - Qiita](https://qiita.com/TETSURO1999/items/0cc093f427531407d2d4)
- [マージソートを非再帰型に書き直す～誰でも思いつくアイディアだが～ - Qiita](https://qiita.com/TETSURO1999/items/23bdd493975cbd8a5085)
- [マージソートを非再帰型に書き直す２～さらなる改善を試みる～ - Qiita](https://qiita.com/TETSURO1999/items/783aa5732b9f19a615ca)
- [マージソートを非再帰型に書き直す３～もう限界かもしれない～ - Qiita](https://qiita.com/TETSURO1999/items/5aa007604198b2ff7b06)
- [マージソートを非再帰型に書き直す４～限界突破のアイディアを思いつく～ - Qiita](https://qiita.com/TETSURO1999/items/17d751555fcf9b275518)


しかしながら，そもそもは .NET (Framework) の `Array.Sort` の謎が発端である。

- [数万個のファイルの重複チェックを行うプログラムをC#でささっと作る２～コメント欄で指導されて作り直す - Qiita](https://qiita.com/TETSURO1999/items/0cc068456552a65ae486)
- [数万個のファイルの重複チェックを行うプログラムをC#でささっと作る３～.NETのArray.Sortの謎に挑む - Qiita](https://qiita.com/TETSURO1999/items/68422ff100dbecf2ff1a)

本命は .NET (Framework) の `Array.Sort` でありながら，一見回り道をしてきたのは理由がある。単純に `Array.Sort` のソースコードが巨大すぎて筆者の理解能力を超えているからだ。

<table>
<caption>表１　ソート関数のソースコード比較<caption>
<thead>
<tr><th></th>
    <th>ファイル名</th>
    <th>ステップ数</th>
    <th>ファイルサイズ</th></tr>
</thead>
<tbody>
<tr></tr>
<tr><th>uCRT</th>
    <td> qsort.cpp</td>
    <td style="text-align:right">396行</td>
    <td style="text-align:right">12,904 bytes</td></tr>
<tr></tr>
<tr><th>GNU C library</th>
    <td> qsort.c</td>
    <td style="text-align:right">407行</td>
    <td style="text-align:right">10,507 bytes</td></tr>
<tr></tr>
<tr><th>.NET Framework 4.8</th>
    <td>array.cs</td>
    <td style="text-align:right">3083行</td>
    <td style="text-align:right">137,701 bytes</td></tr>
<tr></tr>
<tr><th>.NET</th>
    <td>array.cs</td>
    <td style="text-align:right">2578行</td>
    <td style="text-align:right">107,786 bytes</td></tr>
</table>

各ソースコードは以下を参照した。

- qsort.cpp - uCRT
  Visual Studio 2022 Community Edition をインストールすると下記フォルダにあるはず。
  `C:\Program Files (x86)\Windows Kits\10\Source\10.0.26100.0\ucrt\stdlib\qsort.cpp`
- [GNU C Library 2.41 stdlib/qsort.c - glibc.git](https://sourceware.org/git/?p=glibc.git;a=blob_plain;f=stdlib/qsort.c;hb=e5893e6349541d871e8a25120bca014551d13ff5)
- [Array.cs - .NET Framework 4.8](https://referencesource.microsoft.com/#mscorlib/system/array.cs)
- [Array.cs (.NET Platform) - github](https://github.com/dotnet/runtime/blob/5535e31a712343a63f5d7d796cd874e563e5ac14/src/libraries/System.Private.CoreLib/src/System/Array.cs)


# テストコード

ということで，まずはソースコードについては触れず，外部からデータを与えて挙動を見ることにした。XorShift による乱数配列を 20～200,000,000 個の範囲で与え，これを昇順ソートさせたときの比較関数の呼び出し回数をカウントする。

比較対象は下記の四つとする。

<table>
<caption>表２　比較対象</caption>
<thead>
<tr><th>言語</th>
    <th>関数</th>
    <th>プラットフォーム</th></tr>
</thead>
<tbody>
<tr></tr>
<tr><th>C</th><th>qsort</th><td>uCRT</td></tr>
<tr></tr>
<tr><th rowspan=5>C#</th>
    <th rowspan=5>Array.Sort</th><td>.NET Framework 3.5</td></tr>
<tr></tr>
<tr><td>.NET Framework 4.8</td></tr>
<tr></tr>
<tr><td>.NET 8.0</td></tr>
</tbody>
</table>

## C言語版テストコード

C 言語版のテストコードを以下に示す。

```c++:test.c
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <string.h>
uint32_t	xorshift(void) {
static	uint64_t	x = 1;
	x ^= x << 13;
	x ^= x >>  7;
	x ^= x << 17;
	return (uint32_t)x;
}
static	uint64_t	count = 0;
static	int		compare(int *p, int *q) {
	count++;
	return *p - *q;
}
int	main(int argc, char *argv[]) {
	if(argc < 3) {
		fprintf(stderr, "Usage: test(.exe) [z/a/d/r] [size]\n");
		return -1;
	}
	int	size = atoi(argv[2]);
	int	*table = malloc(sizeof(int) * size);
	if(table == (int*)NULL) {
		fprintf(stderr, "cannot allocate size: %d\n", size);
		return -1;
	}
	switch(argv[1][0]) {
	  case 'Z': case 'z':	/* ZERO */
		for(int i = 0; i < size; i++) table[i] = 0;
		break;
	  case 'A': case 'a':	/* ASCEND */
		for(int i = 0; i < size; i++) table[i] = i;
		break;
	  case 'D': case 'd':	/* DESCEND */
		for(int i = 0; i < size; i++) table[i] = size - i - 1;
		break;
	  case 'R': case 'r':	/* RANDOM */
		for(int i = 0; i < size; i++) table[i] = xorshift() % size;
		break;
	  default:
		fprintf(stderr, "illegal command: %s\n", argv[1]);
		return -1;
	}
	qsort(table, size, sizeof(int), (int(*)(const void*, const void*))compare);
	fprintf(stdout, "%lld\n", count);
	return 0;
}
```

## C#版

C# 版のテストコードを以下に示す。.NET Framework 3.5 or 4.8 および .NET 8.0 のソースコードは共通である。

```C#:test.cs
using System;
using System.IO;
class XorShift {
	private	ulong	x = 1;
	public	XorShift() {}
	public	XorShift(ulong s) {x = s;}
	public	uint	Next() {
		x ^= x << 13;
		x ^= x >>  7;
		x ^= x << 17;
		return (uint)x;
	}
}
class TEST {
	static	int	Main(string[] args) {
		if(args.Length < 2) {
			Console.Error.WriteLine("Usage: test(.exe) [z/a/d/r] [size]");
			return -1;
		}
		var	size = int.Parse(args[1]);
		var	table = new int[size];
		switch(args[0][0]) {
		  case 'Z': case 'z':	/* ZERO */
			for(int i = 0; i < size; i++) table[i] = 0;
			break;
		  case 'A': case 'a':	/* ASCEND */
			for(int i = 0; i < size; i++) table[i] = i;
			break;
		  case 'D': case 'd':	/* DESCEND */
			for(int i = 0; i < size; i++) table[i] = size - i - 1;
			break;
		  case 'R': case 'r':	/* RANDOM */
			var	r = new XorShift();
			for(int i = 0; i < size; i++) table[i] = (int)(r.Next() % size);
			break;
		  default:
			return -1;
		}
		ulong	count = 0;
		Comparison<int> compare = delegate(int a, int b) {
			count++;
			return a - b;
		};
		Array.Sort(table, compare);
		Console.Out.WriteLine(count);
		return 0;
	}
}
```

# ビルド手順

## Visual C++ の場合

Visual Studio 2022 Community Edition だと下記の通り。

```
cl /O2 /W4 test.c
```

## .NET Framework 3.5 の場合

下記のバッチファイルを実行する。人によっては .NET Framework 3.5 をインストールする必要があるかもしれない。

```:net35.cmd
@echo off
setlocal
for /F "usebackq tokens=1,2,*" %%I in (
  `reg query "HKLM\SOFTWARE\Microsoft\NET Framework Setup\NDP\v3.5" /v InstallPath`
) do (
  if "%%I"=="InstallPath" set "DOTNETPATH=%%K"
)
if "%DOTNETPATH:~-1%"=="\" set "DOTNETPATH=%DOTNETPATH:~0,-1%"
set "PATH=%PATH%;%DOTNETPATH%"
if not exist NET35 mkdir NET35
csc -o -w:4 -out:NET35\test.exe test.cs
endlocal
exit /b
```

## .NET Framework 4.8 の場合

下記のバッチファイルを実行する。

```:net48.cmd
@echo off
setlocal
for /F "usebackq tokens=1,2,*" %%I in (
  `reg query "HKLM\SOFTWARE\Microsoft\NET Framework Setup\NDP\v4\Full" /v InstallPath`
) do (
  if "%%I"=="InstallPath" set "DOTNETPATH=%%K"
)
if "%DOTNETPATH:~-1%"=="\" set "DOTNETPATH=%DOTNETPATH:~0,-1%"
set "PATH=%PATH%;%DOTNETPATH%"
if not exist NET48 mkdir NET48
csc -o -w:4 -out:NET48\test.exe test.cs
endlocal
exit /b
```

## .NET 8.0 の場合

Visual Studio 2022 Community Edition をインストールしている人は .NET 8.0 が使えるはず。コマンドプロンプト（またはターミナル）で下記のコマンドを実行する。

```
dotnet build -c Release
```

ソースコード `test.cs` と同じフォルダに下記のプロジェクトファイル `test.csproj` を置いておくこと。

```xml:test.csproj
<Project Sdk="Microsoft.NET.Sdk">
  <PropertyGroup>
    <OutputType>Exe</OutputType>
    <TargetFramework>net8.0</TargetFramework>
    <ImplicitUsings>enable</ImplicitUsings>
    <Nullable>enable</Nullable>
    <EnableDefaultCompileItems>false</EnableDefaultCompileItems>
  </PropertyGroup>
  <ItemGroup>
    <Compile Include="test.cs" />
  </ItemGroup>
</Project>
```

# テスト手順

下記のバッチファイルを実行する。

```:run.cmd
@echo off
for %%H in (
  test.exe
  NET35\test.exe
  NET48\test.exe
  bin\Release\net8.0\test.exe
) do (
  echo %%H
  for %%I in (
    20 50
    100 200 500
    1000 2000 5000
    10000 20000 50000
    100000 200000 500000
    1000000 2000000 5000000
    10000000 20000000 50000000
    100000000 200000000
  ) do (
    %%H random %%I
  )
)
exit /b
```

# テスト結果

テスト結果を以下に示す。

<table>
<caption>表１　乱数の昇順ソートに費やす比較関数の呼び出し回数</caption>
<thead>
<tr><th style="text-align:center">要素数<br>$N$</th>
    <th style="text-align:center">qsort(uCRT)</th>
    <th style="text-align:center">.NET<br>Framework<br>3.5</th>
    <th style="text-align:center">.NET<br>Framework<br>4.8</th>
    <th style="text-align:center">.NET 8.0</th></tr>
</thead>
<tbody>
<tr><td style="text-align:right">20</td>
    <td style="text-align:right">84</td>
    <td style="text-align:right">133</td>
    <td style="text-align:right">133</td>
    <td style="text-align:right">56</td></tr>
<tr><td style="text-align:right">50</td>
    <td style="text-align:right">307</td>
    <td style="text-align:right">396</td>
    <td style="text-align:right">396</td>
    <td style="text-align:right">267</td></tr>
<tr><td style="text-align:right">100</td>
    <td style="text-align:right">703</td>
    <td style="text-align:right">938</td>
    <td style="text-align:right">938</td>
    <td style="text-align:right">663</td></tr>
<tr><td style="text-align:right">200</td>
    <td style="text-align:right">1,740</td>
    <td style="text-align:right">2,227</td>
    <td style="text-align:right">2,227</td>
    <td style="text-align:right">1,496</td></tr>
<tr><td style="text-align:right">500</td>
    <td style="text-align:right">5,030</td>
    <td style="text-align:right">6,388</td>
    <td style="text-align:right">6,388</td>
    <td style="text-align:right">4,594</td></tr>
<tr><td style="text-align:right">1,000</td>
    <td style="text-align:right">11,160</td>
    <td style="text-align:right">14,241</td>
    <td style="text-align:right">14,241</td>
    <td style="text-align:right">10,196</td></tr>
<tr><td style="text-align:right">2,000</td>
    <td style="text-align:right">25,238</td>
    <td style="text-align:right">29,184</td>
    <td style="text-align:right">29,184</td>
    <td style="text-align:right">23,226</td></tr>
<tr><td style="text-align:right">5,000</td>
    <td style="text-align:right">76,025</td>
    <td style="text-align:right">83,449</td>
    <td style="text-align:right">83,449</td>
    <td style="text-align:right">67,737</td></tr>
<tr><td style="text-align:right">10,000</td>
    <td style="text-align:right">155,041</td>
    <td style="text-align:right">177,783</td>
    <td style="text-align:right">177,783</td>
    <td style="text-align:right">147,400</td></tr>
<tr><td style="text-align:right">20,000</td>
    <td style="text-align:right">327,934</td>
    <td style="text-align:right">369,599</td>
    <td style="text-align:right">369,599</td>
    <td style="text-align:right">304,244</td></tr>
<tr><td style="text-align:right">50,000</td>
    <td style="text-align:right">897,936</td>
    <td style="text-align:right">1,043,028</td>
    <td style="text-align:right">1,043,028</td>
    <td style="text-align:right">884,113</td></tr>
<tr><td style="text-align:right">100,000</td>
    <td style="text-align:right">1,945,323</td>
    <td style="text-align:right">2,179,318</td>
    <td style="text-align:right">2,179,318</td>
    <td style="text-align:right">1,811,675</td></tr>
<tr><td style="text-align:right">200,000</td>
    <td style="text-align:right">4,169,217</td>
    <td style="text-align:right">4,486,461</td>
    <td style="text-align:right">4,486,446</td>
    <td style="text-align:right">3,833,795</td></tr>
<tr><td style="text-align:right">500,000</td>
    <td style="text-align:right">10,990,027</td>
    <td style="text-align:right">12,277,948</td>
    <td style="text-align:right">12,277,110</td>
    <td style="text-align:right">10,640,989</td></tr>
<tr><td style="text-align:right">1,000,000</td>
    <td style="text-align:right">22,924,973</td>
    <td style="text-align:right">25,373,361</td>
    <td style="text-align:right">25,372,150</td>
    <td style="text-align:right">21,979,476</td></tr>
<tr><td style="text-align:right">2,000,000</td>
    <td style="text-align:right">48,497,868</td>
    <td style="text-align:right">54,838,178</td>
    <td style="text-align:right">54,783,339</td>
    <td style="text-align:right">47,406,196</td></tr>
<tr><td style="text-align:right">5,000,000</td>
    <td style="text-align:right">130,345,910</td>
    <td style="text-align:right">140,192,513</td>
    <td style="text-align:right">140,073,583</td>
    <td style="text-align:right">124,619,124</td></tr>
<tr><td style="text-align:right">10,000,000</td>
    <td style="text-align:right">272,197,148</td>
    <td style="text-align:right">297,639,739</td>
    <td style="text-align:right">296,475,127</td>
    <td style="text-align:right">262,655,755</td></tr>
<tr><td style="text-align:right">20,000,000</td>
    <td style="text-align:right">566,211,699</td>
    <td style="text-align:right">619,190,596</td>
    <td style="text-align:right">615,415,448</td>
    <td style="text-align:right">553,305,269</td></tr>
<tr><td style="text-align:right">50,000,000</td>
    <td style="text-align:right">1,483,365,911</td>
    <td style="text-align:right">1,601,171,234</td>
    <td style="text-align:right">1,586,737,108</td>
    <td style="text-align:right">1,445,233,081</td></tr>
<tr><td style="text-align:right">100,000,000</td>
    <td style="text-align:right">3,066,511,691</td>
    <td style="text-align:right">3,317,171,348</td>
    <td style="text-align:right">3,275,574,132</td>
    <td style="text-align:right">2,972,257,226</td></tr>
<tr><td style="text-align:right">200,000,000</td>
    <td style="text-align:right">6,400,427,154</td>
    <td style="text-align:right">6,916,900,788</td>
    <td style="text-align:right">6,804,184,853</td>
    <td style="text-align:right">6,213,723,201</td></tr>
</tbody>
</table>

クイックソートの計算量は $O(N \log{N})$  であるとされているので，その比例係数 $K$ を求めた。配列の要素数 $N$，比較関数の呼び出し回数 $M$ とおくと

```math
K = \frac{M}{N \log_{10}{N}}
```

とする。グラフにすると分かり易い。.NET Framework 3.5 および 4.8 は qsort (uCRT) と比べて 比較関数の呼び出し回数が多いが，.NET 8.0 になると逆転する。

<font color=#5B9BD5>■</font>qsort (uCRT)，<font color=#ED7D31>■</font>.NET Framework 3.5，<font color=#A5A5A5>■</font>.NET Framework 4.8，<font color=#FFC000>■</font>.NET 8.0

```plantuml
@startuml
<style>
root {
  margin 0
  padding 0
}
title {
  fontStyle normal
  fontSize 16
}
</style>
sprite FIGURE <svg width="610" height="440">
<g fill="lightgray">
<path d="M30 20 h560 v1 h-560">
<path d="M30 80 h560 v1 h-560">
<path d="M30 140 h560 v1 h-560">
<path d="M30 200 h560 v1 h-560">
<path d="M30 260 h560 v1 h-560">
<path d="M30 320 h560 v1 h-560">
<path d="M30 380 h560 v1 h-560">
<path d="M30 20 v360 h1 v-360">
<path d="M110 20 v360 h1 v-360">
<path d="M190 20 v360 h1 v-360">
<path d="M270 20 v360 h1 v-360">
<path d="M350 20 v360 h1 v-360">
<path d="M430 20 v360 h1 v-360">
<path d="M510 20 v360 h1 v-360">
<path d="M590 20 v360 h1 v-360">
</g>
<g fill="#5B9BD5">
<path d="M51.1 185.3 h36.2 v2 h-36.2" transform="rotate(-39.7,51.1,186.3)">
<path d="M78.9 162.2 h21.9 v2 h-21.9" transform="rotate(15.7,78.9,163.2)">
<path d="M100 168.1 h26.4 v2 h-26.4" transform="rotate(-37.1,100,169.1)">
<path d="M121.1 152.1 h28 v2 h-28" transform="rotate(6.6,121.1,153.1)">
<path d="M148.9 155.4 h21.2 v2 h-21.1" transform="rotate(1.2,148.9,156.4)">
<path d="M170 155.8 h22 v2 h-22" transform="rotate(-16.3,170,156.8)">
<path d="M191.1 149.6 h32.8 v2 h-32.8" transform="rotate(-31.8,191.1,150.6)">
<path d="M218.9 132.4 h25.3 v2 h-25.3" transform="rotate(33.7,218.9,133.4)">
<path d="M240 146.4 h21.4 v2 h-21.4" transform="rotate(10.3,240,147.4)">
<path d="M261.1 150.3 h27.9 v2 h-27.9" transform="rotate(-1.2,261.1,151.3)">
<path d="M288.9 149.7 h21.5 v2 h-21.5" transform="rotate(-11.1,288.9,150.7)">
<path d="M310 145.6 h21.2 v2 h-21.2" transform="rotate(-6.8,310,146.6)">
<path d="M331.1 143.1 h28.2 v2 h-28.2" transform="rotate(9.3,331.1,144.1)">
<path d="M358.9 147.6 h21.2 v2 h-21.2" transform="rotate(5.9,358.9,148.6)">
<path d="M380 149.8 h21.1 v2 h-21.1" transform="rotate(-4.5,380,150.8)">
<path d="M401.1 148.1 h28 v2 h-28" transform="rotate(-5.3,401.1,149.1)">
<path d="M428.9 145.5 h21.1 v2 h-21.1" transform="rotate(0.5,428.9,146.5)">
<path d="M450 145.7 h21.1 v2 h-21.1" transform="rotate(1.8,450,146.7)">
<path d="M471.1 146.3 h27.9 v2 h-27.9" transform="rotate(3,471.1,147.3)">
<path d="M498.9 147.8 h21.1 v2 h-21.1" transform="rotate(3.3,498.9,148.8)">
<path d="M520 149 h21.1 v2 h-21.1" transform="rotate(-3.6,520,150)">
</g>
<g fill="#ED7D31">
<path d="M51.1 72.3 h38.8 v2 h-38.8" transform="rotate(44.1,51.1,73.3)">
<path d="M78.9 99.3 h21.1 v2 h-21.1" transform="rotate(-4.6,78.9,100.3)">
<path d="M100 97.6 h22.9 v2 h-22.9" transform="rotate(-23,100,98.6)">
<path d="M121.1 88.7 h28.6 v2 h-28.6" transform="rotate(12.8,121.1,89.7)">
<path d="M148.9 95 h21.1 v2 h-21.1" transform="rotate(-2.2,148.9,96)">
<path d="M170 94.2 h28.8 v2 h-28.8" transform="rotate(42.9,170,95.2)">
<path d="M191.1 113.8 h28.4 v2 h-28.4" transform="rotate(-11.2,191.1,114.8)">
<path d="M218.9 108.3 h21.5 v2 h-21.5" transform="rotate(10.9,218.9,109.3)">
<path d="M240 112.3 h22.9 v2 h-22.9" transform="rotate(22.8,240,113.3)">
<path d="M261.1 121.2 h29.1 v2 h-29.1" transform="rotate(-17.1,261.1,122.2)">
<path d="M288.9 112.6 h21.6 v2 h-21.6" transform="rotate(12.9,288.9,113.6)">
<path d="M310 117.5 h22.4 v2 h-22.4" transform="rotate(19.9,310,118.5)">
<path d="M331.1 125.1 h28.2 v2 h-28.2" transform="rotate(-9.4,331.1,126.1)">
<path d="M358.9 120.5 h21.6 v2 h-21.6" transform="rotate(12.8,358.9,121.5)">
<path d="M380 125.3 h22.3 v2 h-22.3" transform="rotate(-19.2,380,126.3)">
<path d="M401.1 117.9 h29.6 v2 h-29.6" transform="rotate(19.7,401.1,118.9)">
<path d="M428.9 127.9 h21.4 v2 h-21.4" transform="rotate(-10.7,428.9,128.9)">
<path d="M450 123.9 h21.1 v2 h-21.1" transform="rotate(1.9,450,124.9)">
<path d="M471.1 124.6 h28.3 v2 h-28.3" transform="rotate(9.9,471.1,125.6)">
<path d="M498.9 129.4 h21.1 v2 h-21.1" transform="rotate(2.1,498.9,130.4)">
<path d="M520 130.2 h21.1 v2 h-21.1" transform="rotate(-3.2,520,131.2)">
</g>
<g fill="#A5A5A5">
<path d="M51.1 72.3 h38.8 v2 h-38.8" transform="rotate(44.1,51.1,73.3)">
<path d="M78.9 99.3 h21.1 v2 h-21.1" transform="rotate(-4.6,78.9,100.3)">
<path d="M100 97.6 h22.9 v2 h-22.9" transform="rotate(-23,100,98.6)">
<path d="M121.1 88.7 h28.6 v2 h-28.6" transform="rotate(12.8,121.1,89.7)">
<path d="M148.9 95 h21.1 v2 h-21.1" transform="rotate(-2.2,148.9,96)">
<path d="M170 94.2 h28.8 v2 h-28.8" transform="rotate(42.9,170,95.2)">
<path d="M191.1 113.8 h28.4 v2 h-28.4" transform="rotate(-11.2,191.1,114.8)">
<path d="M218.9 108.3 h21.5 v2 h-21.5" transform="rotate(10.9,218.9,109.3)">
<path d="M240 112.3 h22.9 v2 h-22.9" transform="rotate(22.8,240,113.3)">
<path d="M261.1 121.2 h29.1 v2 h-29.1" transform="rotate(-17.1,261.1,122.2)">
<path d="M288.9 112.6 h21.6 v2 h-21.6" transform="rotate(12.9,288.9,113.6)">
<path d="M310 117.5 h22.4 v2 h-22.4" transform="rotate(19.9,310,118.5)">
<path d="M331.1 125.1 h28.2 v2 h-28.2" transform="rotate(-9.4,331.1,126.1)">
<path d="M358.9 120.5 h21.6 v2 h-21.6" transform="rotate(12.8,358.9,121.5)">
<path d="M380 125.3 h22.2 v2 h-22.2" transform="rotate(-18.6,380,126.3)">
<path d="M401.1 118.2 h29.6 v2 h-29.6" transform="rotate(19.6,401.1,119.2)">
<path d="M428.9 128.1 h21.3 v2 h-21.3" transform="rotate(-8.6,428.9,129.1)">
<path d="M450 124.9 h21.1 v2 h-21.1" transform="rotate(3.4,450,125.9)">
<path d="M471.1 126.1 h28.4 v2 h-28.4" transform="rotate(11.3,471.1,127.1)">
<path d="M498.9 131.7 h21.1 v2 h-21.1" transform="rotate(4.5,498.9,132.7)">
<path d="M520 133.3 h21.1 v2 h-21.1" transform="rotate(-0.6,520,134.3)">
</g>
<g fill="#FFC000">
<path d="M51.1 249.9 h65.7 v2 h-65.7" transform="rotate(-64.9,51.1,250.9)">
<path d="M78.9 190.4 h23.5 v2 h-23.5" transform="rotate(-26.1,78.9,191.4)">
<path d="M100 180.1 h21.4 v2 h-21.4" transform="rotate(10.4,100,181.1)">
<path d="M121.1 184 h29.3 v2 h-29.3" transform="rotate(-18.3,121.1,185)">
<path d="M148.9 174.7 h21.1 v2 h-21.1" transform="rotate(0.9,148.9,175.7)">
<path d="M170 175.1 h22.3 v2 h-22.3" transform="rotate(-18.8,170,176.1)">
<path d="M191.1 167.9 h29.2 v2 h-29.2" transform="rotate(-17.3,191.1,168.9)">
<path d="M218.9 159.3 h21.1 v2 h-21.1" transform="rotate(-3.7,218.9,160.3)">
<path d="M240 157.9 h22.9 v2 h-22.9" transform="rotate(22.9,240,158.9)">
<path d="M261.1 166.8 h31 v2 h-31" transform="rotate(-26,261.1,167.8)">
<path d="M288.9 153.2 h22.7 v2 h-22.7" transform="rotate(21.7,288.9,154.2)">
<path d="M310 161.6 h21.1 v2 h-21.1" transform="rotate(1.2,310,162.6)">
<path d="M331.1 162 h28.7 v2 h-28.7" transform="rotate(-14.3,331.1,163)">
<path d="M358.9 154.9 h21.5 v2 h-21.5" transform="rotate(11.4,358.9,155.9)">
<path d="M380 159.2 h21.9 v2 h-21.9" transform="rotate(-15.7,380,160.2)">
<path d="M401.1 153.3 h28 v2 h-28" transform="rotate(5.1,401.1,154.3)">
<path d="M428.9 155.8 h21.2 v2 h-21.2" transform="rotate(-5.2,428.9,156.8)">
<path d="M450 153.9 h21.2 v2 h-21.2" transform="rotate(-6,450,154.9)">
<path d="M471.1 151.6 h27.9 v2 h-27.9" transform="rotate(4.3,471.1,152.6)">
<path d="M498.9 153.7 h21.2 v2 h-21.2" transform="rotate(6.3,498.9,154.7)">
<path d="M520 156.1 h21.1 v2 h-21.1" transform="rotate(-4.5,520,157.1)">
</g>
<text x="14" y="386" font-size="16" fill="black">0</text>
<text x="14" y="326" font-size="16" fill="black">1</text>
<text x="14" y="266" font-size="16" fill="black">2</text>
<text x="14" y="206" font-size="16" fill="black">3</text>
<text x="14" y="146" font-size="16" fill="black">4</text>
<text x="14" y="86" font-size="16" fill="black">5</text>
<text x="14" y="26" font-size="16" fill="black">6</text>
<text x="20" y="400" font-size="16" fill="black">10</text>
<text x="100" y="400" font-size="16" fill="black">10²</text>
<text x="180" y="400" font-size="16" fill="black">10³</text>
<text x="260" y="400" font-size="16" fill="black">10⁴</text>
<text x="340" y="400" font-size="16" fill="black">10⁵</text>
<text x="420" y="400" font-size="16" fill="black">10⁶</text>
<text x="500" y="400" font-size="16" fill="black">10⁷</text>
<text x="580" y="400" font-size="16" fill="black">10⁸</text>
<text x="260" y="420" font-size="16" fill="black">配列の要素数</text>
</svg>
title
<$FIGURE>
図１　比例係数 <math>K</math> の比較
end title
@enduml
```

# 結論

.NET Framework 3.5 と 4.8 は途中まで（$N \le 100000$）は同じであるが，それより $N$ が大きくなると微妙に異なる。.NET Framework 3.5 のソースコードは公開されていないようなので細かい仕様が分からないが，$N$ が小さいときのソートアルゴリズム（クイックソート）は .NET Framework 4.8 と共通なものを使用していると考えらえる。これを仮に **quicksort(A)** と呼ぶことにする。

.NET Framework 3.5 では，この **quicksort(A)** を全面的に採用していると思われる。このため平均的には $O(N \log N)$ の計算量で済むが，最悪ケースでは $O(N^2)$ となることを避けられないはずだ。

次に .NET Framework 4.8 では **quicksort(A)** を用いてソートを開始するが，再帰関数の呼び出し深さ $d > 32$ となるとヒープソートに切り替えることで最悪ケースを回避していると思われる。

一方 .NET 8.0 ではベースとなるクイックソートが改善されており，比較回数が少なくなっている。区別するために **quicksort(B)** と呼ぼう。再帰関数の呼び出しが深くなるとヒープソートに切り替えるが，切り替えの閾値は固定値ではなく，配列の要素数 $N$ として $d > 2(\log_2{N} + 1)$ としている。また，クイックソートによって分割された区間のサイズ $n \le 16$ になると挿入ソートに切り替わる。

このようにクイックソートでスタートして，再帰関数の呼び出し深さが閾値を超えるとヒープソートに切り替わるようなアルゴリズムをイントロソートと呼ぶ。

```plantuml
@startuml
<style>
root {
  margin 0
  padding 0
}
title {
  fontStyle normal
  fontSize 16
}
</style>
sprite FIGURE <svg width="600" height="460">
<path d="M40  400 h160 v-360 h-160" fill="lightyellow">
<path d="M220 400 h160 v-180 h-160" fill="lightyellow">
<path d="M220 220 h160 v-180 h-160" fill="pink">
<path d="M400 160 h160 v-120 h-160" fill="pink">
<path d="M400 280 h160 v-120 h-160" fill="yellow">
<path d="M400 400 h160 v-120 h-160" fill="lightgreen">
<g fill="black">
<path d="M40 400 h160 v1 h-160">
<path d="M40  40 h160 v1 h-160">
<path d="M40  400 v-360 h1 v360">
<path d="M200 400 v-360 h1 v360">
<path d="M220 400 h160 v1 h-160">
<path d="M220 220 h160 v1 h-160">
<path d="M220  40 h160 v1 h-160">
<path d="M220 400 v-360 h1 v360">
<path d="M380 400 v-360 h1 v360">
<path d="M400 400 h160 v1 h-160">
<path d="M400 280 h160 v1 h-160">
<path d="M400 160 h160 v1 h-160">
<path d="M400  40 h160 v1 h-160">
<path d="M400 400 v-360 h1 v360">
<path d="M560 400 v-360 h1 v360">
</g>
<text x="40"  y="420" font-size="16" fill="black">.NET Framework 3.5</text>
<text x="220" y="420" font-size="16" fill="black">.NET Framework 4.8</text>
<text x="445" y="420" font-size="16" fill="black">.NET 8.0</text>
<text x="75"  y="226" font-size="16" fill="black">quicksort(A)</text>
<text x="255" y="310" font-size="16" fill="black">quicksort(A)</text>
<text x="280" y="328" font-size="16" fill="black">d≦32</text>
<text x="265" y="130" font-size="16" fill="black">heapsort</text>
<text x="277" y="148" font-size="16" fill="black">d>32</text>
<text x="435" y="220" font-size="16" fill="black">quicksort(B)</text>
<text x="428" y="238" font-size="16" fill="black">d≦2(log₂N+1)</text>
<text x="445" y="100" font-size="16" fill="black">heapsort</text>
<text x="425" y="118" font-size="16" fill="black">d>2(log₂N+1)</text>
<text x="428" y="340" font-size="16" fill="black">insertion sort</text>
<text x="456" y="358" font-size="16" fill="black">n≦16</text>
</svg>
title
<$FIGURE>
図２　.NET (Framework) の Array.Sort の分担
end title
@enduml
```

なお .NET Framework 4.8 のヒープソートと .NET 8.0 のヒープソートが同じものかどうかは確定していない。確かめようにもヒープソートが必要になる最悪データを作ることが出来ていないからだ。

# 参考文献

- [.NET4.5と.NET4のソートは結果が異なる - Qiita](https://qiita.com/shuetsu@github/items/a58bd707a2dbf90fd35c)