クイックソートキラーを作る

# はじめに

筆者の過去記事の続きである。

https://qiita.com/TETSURO1999/items/85a92b64ee463725c734

.NET Framework 4.5 以降の `Array.Sort` はイントロソートを採用しており，平均的なデータに対しては高速とされるクイックソートでソートを開始するが，クイックソートでは時間がかかる場合は途中でヒープソートに切り替わる。

.NET Framework 4.8 の `Array.Sort` では，単に再帰関数の呼び出し深さが 32 を超えるとヒープソートに切り替えるため，ある程度以上の大規模なデータを与えてやればヒープソートに切り替わる。

しかし，.NET Core 以降では，ヒープソートへ切り替わる再帰関数の呼び出し深さは与えたデータ点数の対数に比例するようになっており，単に大規模な乱数データを与えただけではヒープソートへの切り替えを確認できなかった。

本当にヒープソートに切り替わるのか確認するため，クイックソートでは $O(n^2)$ の時間がかかるようなデータを作成したい。

# クイックソートの原理

クイックソートとはピボットと呼ばれる数値を選び，ピボットと配列のデータの大小比較を行って領域を二つのグループに分ける。そして分割したグループ毎に新たにピボットを選んで領域を細分割していくという再帰的なアルゴリズムである。理想としては二つの領域を等分割したいが，無作為に選んだピボットが都合よく領域の中央値になるとは限らないので，一般的には非均等分割になる。しかし，平均的には等分割される場合と大差なく $O(n \log n)$ の計算量で済むことが期待されている。しかし，選んだピボットが運悪く領域の最小値または最大値で<ruby>あり続ける<rt>●●●●●</rt></ruby>と $O(n^2)$ の計算量になってしまう。

このようにピボットが領域の最小値または最大値で<ruby>あり続ける<rt>●●●●●</rt></ruby>最悪なデータを作成するにはどうすれば良いだろうか？

ソースコードが公開されているものについては，そのアルゴリズムに応じて最悪データを作ればよい。たいていの実装ではピボットの値が偏らないように先頭と末尾，そして中間の三点でサンプリングを行うが，uCRT の `qsort` と .NET の `Array.Sort` では中間サンプリングの位置が異なる。配列の要素数 $n$ とおくと uCRT の `qsort` の中間サンプリング位置は $n / 2$ なのに対し，.NET の `Array.Sort` は $(n - 1) / 2$ なので，$n$ が偶数の場合は一つずれるのだ。

という訳で各実装に応じてデータを作るのは面倒だなと思っていた。

# クイックソートキラーの原理


先日，クイックソートキラーの存在を知った。たいていのクイックソート関数は任意の比較関数を指定できるので，その比較関数にピボット位置を探すコードを仕込ませるというアイディアだ[^1][^2]。

クイックソートでは最初期にピボットとなる値を決め，ピボットを基準として全データを舐めるように比較していくので，最初期に呼び出されるのがピボット（候補）であり，ピボットにはできるだけ小さな値を割り当てる。以後，ピボットとの比較を繰り返すが，ピボットと比較される値については具体的な値を決めずに（遅延評価）ピボットが最小値であることから大小関係のみを返してやればいい。

コレ，最初に思いついた人天才だな。

# アルゴリズム概要

参考文献のサイトを自分なりに解釈して作り直したものを以下示す。

## 1. 初期化
配列の要素数 `size` として，クイックソートに引き渡すダミー配列 `dummy[]` とピボットの値を割り当てる配列 `pivot[]` を確保する。ダミー配列 `dummy[]` は昇順データとし，ピボット配列 `pivot[]` は未定義値として負の値で初期化する。

```c#:初期化
var dummy = new int[size];
var pivot = new int[size];
for(int i = 0; i < size; i++) dummy[i] = i;
for(int i = 0; i < size; i++) pivot[i] = -1;
```

## 2. キラー関数

二つの引数がいずれも未定義の場合，両者をピボット（候補）として値を割り当てる。割り当てる値は最初期がもっとも小さく，徐々に大きくしていく。

二つの引数のうち一方がピボットの場合，もう一方の値は具体的に決めず（遅延評価），ピボットのほうが必ず小さいものとして大小関係のみを返す。

ピボット同士を比較する場合のみ割り当てた値同士で比較する。

```c#:キラー関数
int     index = 0;
Comparison<int> killer = delegate(int a, int b) {
    if(pivot[a] < 0 && pivot[b] < 0) {
        pivot[a] = index++;
        pivot[b] = index++;
        return -1;
    }
    if(pivot[a] < 0) return  1;
    if(pivot[b] < 0) return -1;
    return pivot[a] - pivot[b];
};
Array.Sort(dummy, killer);
```

ちなみに，この実行自体 $O(n^2)$ の計算量を要する。

## 3. 最悪データの作成

上記のアルゴリズムに沿ってソートを行うと，もともと昇順でソートされていたダミー配列 `dummy[]` は一見デタラメな順にシャッフルされたように見えるが，$O(n^2)$ の計算量を要するようにソートされた結果であり，貴重な情報を内包している。

```plantuml
@startuml
<style>
root {
  margin 0
  padding 0
}
title {
  fontStyle normal
  fontSize 16
}
</style>
sprite FIGURE <svg width="464" height="192">
<g fill="blue">
<path d="M127 128 v-52 h-3 l4 -12 l4 12 h-3 v52">
<path d="M159 128 v-131.1 h-3 l4 -12 l4 12 h-3 v131.1" transform="rotate(64.4,160,128)">
<path d="M191 128 v-59.6 h-3 l4 -12 l4 12 h-3 v59.6" transform="rotate(26.6,192,128)">
<path d="M223 128 v-59.6 h-3 l4 -12 l4 12 h-3 v59.6" transform="rotate(-26.6,224,128)">
<path d="M255 128 v-103.4 h-3 l4 -12 l4 12 h-3 v103.4" transform="rotate(-56.3,256,128)">
<path d="M287 128 v-59.6 h-3 l4 -12 l4 12 h-3 v59.6" transform="rotate(-26.6,288,128)">
<path d="M319 128 v-59.6 h-3 l4 -12 l4 12 h-3 v59.6" transform="rotate(26.6,320,128)">
<path d="M351 128 v-59.6 h-3 l4 -12 l4 12 h-3 v59.6" transform="rotate(-26.6,352,128)">
<path d="M383 128 v-59.6 h-3 l4 -12 l4 12 h-3 v59.6" transform="rotate(26.6,384,128)">
<path d="M415 128 v-59.6 h-3 l4 -12 l4 12 h-3 v59.6" transform="rotate(-26.6,416,128)">
</g>
<g fill="black">
<path d="M112 32 h320 v1 h-320">
<path d="M112 64 h320 v1 h-320">
<path d="M112 32 v32 h1 v-32">
<path d="M144 32 v32 h1 v-32">
<path d="M176 32 v32 h1 v-32">
<path d="M208 32 v32 h1 v-32">
<path d="M240 32 v32 h1 v-32">
<path d="M272 32 v32 h1 v-32">
<path d="M304 32 v32 h1 v-32">
<path d="M336 32 v32 h1 v-32">
<path d="M368 32 v32 h1 v-32">
<path d="M400 32 v32 h1 v-32">
<path d="M432 32 v32 h1 v-32">
<path d="M112 128 h320 v1 h-320">
<path d="M112 160 h320 v1 h-320">
<path d="M112 128 v32 h1 v-32">
<path d="M144 128 v32 h1 v-32">
<path d="M176 128 v32 h1 v-32">
<path d="M208 128 v32 h1 v-32">
<path d="M240 128 v32 h1 v-32">
<path d="M272 128 v32 h1 v-32">
<path d="M304 128 v32 h1 v-32">
<path d="M336 128 v32 h1 v-32">
<path d="M368 128 v32 h1 v-32">
<path d="M400 128 v32 h1 v-32">
<path d="M432 128 v32 h1 v-32">
</g>
<text x="32" y="54"  fill="black" font-size="16">ソート前</text>
<text x="120" y="54" font-size="16" fill="black">０</text>
<text x="152" y="54" font-size="16" fill="black">１</text>
<text x="184" y="54" font-size="16" fill="black">２</text>
<text x="216" y="54" font-size="16" fill="black">３</text>
<text x="248" y="54" font-size="16" fill="black">４</text>
<text x="280" y="54" font-size="16" fill="black">５</text>
<text x="312" y="54" font-size="16" fill="black">６</text>
<text x="344" y="54" font-size="16" fill="black">７</text>
<text x="376" y="54" font-size="16" fill="black">８</text>
<text x="408" y="54" font-size="16" fill="black">９</text>

<text x="32" y="150" fill="black" font-size="16">ソート後</text>
<text x="120" y="150" font-size="16" fill="black">０</text>
<text x="152" y="150" font-size="16" fill="black">５</text>
<text x="184" y="150" font-size="16" fill="black">３</text>
<text x="216" y="150" font-size="16" fill="black">２</text>
<text x="248" y="150" font-size="16" fill="black">１</text>
<text x="280" y="150" font-size="16" fill="black">４</text>
<text x="312" y="150" font-size="16" fill="black">７</text>
<text x="344" y="150" font-size="16" fill="black">６</text>
<text x="376" y="150" font-size="16" fill="black">９</text>
<text x="408" y="150" font-size="16" fill="black">８</text>
</svg>
title
<$FIGURE>
図１　ソート前後の <font:monospaced>dummy[]</font>
end title
@enduml
```

```plantuml
@startuml
<style>
root {
  margin 0
  padding 0
}
title {
  fontStyle normal
  fontSize 16
}
</style>
sprite FIGURE <svg width="464" height="192">
<g fill="blue">
<path d="M127 128 v-52 h-3 l4 -12 l4 12 h-3 v52">
<path d="M159 128 v-131.1 h-3 l4 -12 l4 12 h-3 v131.1" transform="rotate(64.4,160,128)">
<path d="M191 128 v-59.6 h-3 l4 -12 l4 12 h-3 v59.6" transform="rotate(26.6,192,128)">
<path d="M223 128 v-59.6 h-3 l4 -12 l4 12 h-3 v59.6" transform="rotate(-26.6,224,128)">
<path d="M255 128 v-103.4 h-3 l4 -12 l4 12 h-3 v103.4" transform="rotate(-56.3,256,128)">
<path d="M287 128 v-59.6 h-3 l4 -12 l4 12 h-3 v59.6" transform="rotate(-26.6,288,128)">
<path d="M319 128 v-59.6 h-3 l4 -12 l4 12 h-3 v59.6" transform="rotate(26.6,320,128)">
<path d="M351 128 v-59.6 h-3 l4 -12 l4 12 h-3 v59.6" transform="rotate(-26.6,352,128)">
<path d="M383 128 v-59.6 h-3 l4 -12 l4 12 h-3 v59.6" transform="rotate(26.6,384,128)">
<path d="M415 128 v-59.6 h-3 l4 -12 l4 12 h-3 v59.6" transform="rotate(-26.6,416,128)">
</g>
<g fill="black">
<path d="M112 32 h320 v1 h-320">
<path d="M112 64 h320 v1 h-320">
<path d="M112 32 v32 h1 v-32">
<path d="M144 32 v32 h1 v-32">
<path d="M176 32 v32 h1 v-32">
<path d="M208 32 v32 h1 v-32">
<path d="M240 32 v32 h1 v-32">
<path d="M272 32 v32 h1 v-32">
<path d="M304 32 v32 h1 v-32">
<path d="M336 32 v32 h1 v-32">
<path d="M368 32 v32 h1 v-32">
<path d="M400 32 v32 h1 v-32">
<path d="M432 32 v32 h1 v-32">
<path d="M112 128 h320 v1 h-320">
<path d="M112 160 h320 v1 h-320">
<path d="M112 128 v32 h1 v-32">
<path d="M144 128 v32 h1 v-32">
<path d="M176 128 v32 h1 v-32">
<path d="M208 128 v32 h1 v-32">
<path d="M240 128 v32 h1 v-32">
<path d="M272 128 v32 h1 v-32">
<path d="M304 128 v32 h1 v-32">
<path d="M336 128 v32 h1 v-32">
<path d="M368 128 v32 h1 v-32">
<path d="M400 128 v32 h1 v-32">
<path d="M432 128 v32 h1 v-32">
</g>
<text x="32" y="54"  fill="black" font-size="16">ソート前</text>
<text x="120" y="54" font-size="16" fill="red">０</text>
<text x="152" y="54" font-size="16" fill="red">４</text>
<text x="184" y="54" font-size="16" fill="red">３</text>
<text x="216" y="54" font-size="16" fill="red">２</text>
<text x="248" y="54" font-size="16" fill="red">５</text>
<text x="280" y="54" font-size="16" fill="red">１</text>
<text x="312" y="54" font-size="16" fill="red">７</text>
<text x="344" y="54" font-size="16" fill="red">６</text>
<text x="376" y="54" font-size="16" fill="red">９</text>
<text x="408" y="54" font-size="16" fill="red">８</text>

<text x="32" y="150" fill="black" font-size="16">ソート後</text>
<text x="120" y="150" font-size="16" fill="red">０</text>
<text x="152" y="150" font-size="16" fill="red">１</text>
<text x="184" y="150" font-size="16" fill="red">２</text>
<text x="216" y="150" font-size="16" fill="red">３</text>
<text x="248" y="150" font-size="16" fill="red">４</text>
<text x="280" y="150" font-size="16" fill="red">５</text>
<text x="312" y="150" font-size="16" fill="red">６</text>
<text x="344" y="150" font-size="16" fill="red">７</text>
<text x="376" y="150" font-size="16" fill="red">８</text>
<text x="408" y="150" font-size="16" fill="red">９</text>
</svg>
title
<$FIGURE>
図２　最悪データ <font:monospaced>worst[]</font> の生成
end title
@enduml
```

ソート後のダミー配列 `dummy[]` をソート前の状態に戻す逆関数を考えると，昇順ソート済みの配列に同じ逆関数を与えたものが最悪データ `worst[]` となる。こうして作成した最悪データ `worst[]` を単に昇順ソートさせるだけで $O(n^2)$ の計算量を要するのだ。

```c#:最悪データの作成
var worst = new int[size];
for(int i = 0; i < size; i++)
    worst[dummy[i]] = i;
```

## 4. 備考

なお，ピボット候補に値を割り当てた `pivot[]` をそのまま最悪データとして使っても良いように思える。なぜなら，上記の手順で求めた最悪データ `worst[]` と同様な値を得られるからだ。

```plantuml
@startuml
<style>
root {
  margin 0
  padding 0
}
title {
  fontStyle normal
  fontSize 16
}
</style>
sprite FIGURE <svg width="464" height="192">
<path d="M266 80 v16 h-8 l14 16 l14 -16 h-8 v-16" fill="red">
<g fill="black">
<path d="M112 32 h320 v1 h-320">
<path d="M112 64 h320 v1 h-320">
<path d="M112 32 v32 h1 v-32">
<path d="M144 32 v32 h1 v-32">
<path d="M176 32 v32 h1 v-32">
<path d="M208 32 v32 h1 v-32">
<path d="M240 32 v32 h1 v-32">
<path d="M272 32 v32 h1 v-32">
<path d="M304 32 v32 h1 v-32">
<path d="M336 32 v32 h1 v-32">
<path d="M368 32 v32 h1 v-32">
<path d="M400 32 v32 h1 v-32">
<path d="M432 32 v32 h1 v-32">
<path d="M112 128 h320 v1 h-320">
<path d="M112 160 h320 v1 h-320">
<path d="M112 128 v32 h1 v-32">
<path d="M144 128 v32 h1 v-32">
<path d="M176 128 v32 h1 v-32">
<path d="M208 128 v32 h1 v-32">
<path d="M240 128 v32 h1 v-32">
<path d="M272 128 v32 h1 v-32">
<path d="M304 128 v32 h1 v-32">
<path d="M336 128 v32 h1 v-32">
<path d="M368 128 v32 h1 v-32">
<path d="M400 128 v32 h1 v-32">
<path d="M432 128 v32 h1 v-32">
</g>
<text x="32" y="54"  fill="black" font-size="16">ソート前</text>
<text x="120" y="54" font-size="16" fill="black">-1</text>
<text x="152" y="54" font-size="16" fill="black">-1</text>
<text x="184" y="54" font-size="16" fill="black">-1</text>
<text x="216" y="54" font-size="16" fill="black">-1</text>
<text x="248" y="54" font-size="16" fill="black">-1</text>
<text x="280" y="54" font-size="16" fill="black">-1</text>
<text x="312" y="54" font-size="16" fill="black">-1</text>
<text x="344" y="54" font-size="16" fill="black">-1</text>
<text x="376" y="54" font-size="16" fill="black">-1</text>
<text x="408" y="54" font-size="16" fill="black">-1</text>

<text x="32" y="150" fill="black" font-size="16">ソート後</text>
<text x="120" y="150" font-size="16" fill="black">０</text>
<text x="152" y="150" font-size="16" fill="black">５</text>
<text x="184" y="150" font-size="16" fill="black">３</text>
<text x="216" y="150" font-size="16" fill="black">２</text>
<text x="248" y="150" font-size="16" fill="black">１</text>
<text x="280" y="150" font-size="16" fill="black">４</text>
<text x="312" y="150" font-size="16" fill="black">７</text>
<text x="344" y="150" font-size="16" fill="black">６</text>
<text x="376" y="150" font-size="16" fill="black">９</text>
<text x="408" y="150" font-size="16" fill="black">８</text>
</svg>
title
<$FIGURE>
図３　<font:monospaced>pivot[]</font> は使えないの？
end title
@enduml
```

ただし，今回<ruby>たまたま<rt>●●●●</rt></ruby>同じ値を得られたに過ぎない。配列のサイズやクイックソートの実装によっては `pivot[]` に初期値 `-1` がそのまま残ってしまう場合がある。なので，`pivot[]` を利用したい場合は未定義の初期値には `-1` ではなく，配列の大きさ `size`，あるいはいっそのこと整数最大値である `INT_MAX` のような大きな値を与えたほうが良いだろう。

なお，筆者の確認したところ，uCRT の `qsort` および .NET Framework 3.5 の `Array.Sort` の場合，与えた配列のサイズが偶数の場合は `worst[]` と同じ値が得られるが，奇数の場合は `pivot[]` に `-1` が現れてしまうようだ。



# サンプルコード

サンプルコードを以下に示す。C#版とC言語版の二種類を作成した。

<details><summary><b>サンプルC#版</b></summary>

```c#:ArraySortKiller.cs
using System;
using System.IO;
class ArraySortKiller {
	static	int		Main(string[] args) {
		if(args.Length == 0) {
			Console.Error.WriteLine("Usage: ArraySortKiller(.exe) [size]");
			return -1;
		}
		var	size = int.Parse(args[0]);
		var	dummy = new int[size];
		var	pivot = new int[size];
		for(int i = 0; i < size; i++) dummy[i] = i;
		for(int i = 0; i < size; i++) pivot[i] = -1;
		int		index = 0;
		Comparison<int>	killer = delegate(int a, int b) {
			if(pivot[a] < 0 && pivot[b] < 0) {
				pivot[a] = index++;
				pivot[b] = index++;
				return -1;
			}
			if(pivot[a] < 0) return  1;
			if(pivot[b] < 0) return -1;
			return pivot[a] - pivot[b];
		};
		Array.Sort(dummy, killer);
		var	worst = new int[size];
		for(int i = 0; i < size; i++)
			worst[dummy[i]] = i;
		long	count = 0;
		Comparison<int>	compare = delegate(int a, int b) {
			count++;
			return a - b;
		};
		Array.Sort(worst, compare);
		Console.Out.WriteLine(count);
		return 0;
	}
}
```

</details>

<details><summary><b>サンプルC言語版</b></summary>

```c++:QsortKiller.c
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
static	int			*dummy = (int*)NULL;
static	int			*pivot = (int*)NULL;
static	int			*table = (int*)NULL;
static	int			index = 0;
static	uint64_t	count = 0;
static	int		killer(const int *p, const int *q) {
	if(pivot[*p] < 0 && pivot[*q] < 0) {
		pivot[*p] = index++;
		pivot[*q] = index++;
		return -1;
	}
	if(pivot[*p] < 0) return  1;
	if(pivot[*q] < 0) return -1;
	return pivot[*p] - pivot[*q];
}
static	int		compare(const int *p, const int *q) {
	count++;
	return *p - *q;
}
int	main(int argc, char *argv[]) {
	if(argc < 2) {
		fprintf(stderr, "Usage: QsortKiller(.exe) [size]");
		return -1;
	}
	int	size = atoi(argv[1]);
	if((int*)NULL == (dummy = (int*)malloc(sizeof(int) * size))) {
		fprintf(stderr, "malloc error!!\n");
		return -1;
	}
	if((int*)NULL == (pivot = (int*)malloc(sizeof(int) * size))) {
		fprintf(stderr, "malloc error!!\n");
		return -1;
	}
	for(int i = 0; i < size; i++) dummy[i] = i;
	for(int i = 0; i < size; i++) pivot[i] = -1;
	qsort(dummy, size, sizeof(int), killer);
	free(pivot);
	if((int*)NULL == (worst = (int*)malloc(sizeof(int) * size))) {
		fprintf(stderr, "malloc error!!\n");
		return -1;
	}
	for(int i = 0; i < size; i++)
		worst[dummy[i]] = i;
	free(dummy);
	count = 0;
	qsort(worst, size, sizeof(int), compare);
	fprintf(stdout, "%lld\n", count);
	return 0;
}
```

</details>

# ビルド手順

## Visual C++ の場合
下記のコマンドを実行する。

```
cl /O2 /W4 QsortKiller.c
```

## .NET Framework 3.5 の場合

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

```
@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\ArraySortKiller.exe ArraySortKiller.cs
endlocal
exit /b
```

## .NET Framework 4.8 の場合

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

```
@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\ArraySortKiller.exe ArraySortKiller.cs
endlocal
exit /b
```

## .NET 8.0 の場合

下記のコマンドを実行する。

```
dotnet build -c Release
```

下記のプロジェクトファイルをソースコードと同じフォルダに置くこと。

```xml:ArraySortKiller.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="ArraySortKiller.cs" />
  </ItemGroup>
</Project>
```
# 実行結果

実行結果を以下に示す。uCRT の `qsort` および .NET Framework 3.5 の `Array.Sort` は見事に $O(n^2) \approx n^2/4 $ の計算量（比較関数の呼び出し回数）となっていることが分かる。一方，.NET Framework 4.8 および .NET8.0 のほうは $O(n \log n)$ で収まっており，途中でヒープソートに切り替わっていることが分かる。

<table>
<caption>表１　QuickSort Killer を用いたときの比較関数の呼び出し回数</caption>
<thead>
<tr><th style="text-align:center">要素数<br>$n$</th>
    <th style="text-align:center">Visual C++<br>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">.NET8.0</th></tr>
</thead>
<tbody>
<tr><td style="text-align:right">10</td><td style="text-align:right">39</td><td style="text-align:right">65</td><td style="text-align:right">65</td><td style="text-align:right">13</td></tr>
<tr><td style="text-align:right">20</td><td style="text-align:right">124</td><td style="text-align:right">195</td><td style="text-align:right">195</td><td style="text-align:right">64</td></tr>
<tr><td style="text-align:right">50</td><td style="text-align:right">679</td><td style="text-align:right">885</td><td style="text-align:right">885</td><td style="text-align:right">650</td></tr>
<tr><td style="text-align:right">100</td><td style="text-align:right">2,604</td><td style="text-align:right">3,035</td><td style="text-align:right">2,769</td><td style="text-align:right">1,867</td></tr>
<tr><td style="text-align:right">200</td><td style="text-align:right">10,204</td><td style="text-align:right">11,085</td><td style="text-align:right">7,137</td><td style="text-align:right">4,837</td></tr>
<tr><td style="text-align:right">500</td>
    <td style="text-align:right">63,004</td>
    <td style="text-align:right">65,235</td>
    <td style="text-align:right">21,266</td>
    <td style="text-align:right">15,155</td></tr>
<tr><td style="text-align:right">1,000</td>
    <td style="text-align:right">251,004</td>
    <td style="text-align:right">255,485</td>
    <td style="text-align:right">46,197</td>
    <td style="text-align:right">34,960</td></tr>
<tr><td style="text-align:right">2,000</td>
    <td style="text-align:right">1,002,004</td>
    <td style="text-align:right">1,010,985</td>
    <td style="text-align:right">97,951</td>
    <td style="text-align:right">78,647</td></tr>
<tr><td style="text-align:right">5,000</td>
    <td style="text-align:right">6,255,004</td>
    <td style="text-align:right">6,277,485</td>
    <td style="text-align:right">261,268</td>
    <td style="text-align:right">231,444</td></tr>
<tr><td style="text-align:right">10,000</td>
    <td style="text-align:right">25,010,004</td>
    <td style="text-align:right">25,054,985</td>
    <td style="text-align:right">544,536</td>
    <td style="text-align:right">505,168</td></tr>
<tr><td style="text-align:right">20,000</td>
    <td style="text-align:right">100,020,004</td>
    <td style="text-align:right">100,109,985</td>
    <td style="text-align:right">1,130,597</td>
    <td style="text-align:right">1,090,906</td></tr>
<tr><td style="text-align:right">50,000</td>
    <td style="text-align:right">625,050,004</td>
    <td style="text-align:right">625,274,985</td>
    <td style="text-align:right">2,960,700</td>
    <td style="text-align:right">2,960,448</td></tr>
<tr><td style="text-align:right">100,000</td>
    <td style="text-align:right">2,500,100,004</td>
    <td style="text-align:right">2,500,549,985</td>
    <td style="text-align:right">6,125,482</td>
    <td style="text-align:right">6,326,338</td></tr>
<tr><td style="text-align:right">200,000</td>
    <td style="text-align:right">10,000,200,004</td>
    <td style="text-align:right">10,001,099,985</td>
    <td style="text-align:right">12,661,996</td>
    <td style="text-align:right">13,466,784</td></tr>
<tr><td style="text-align:right">500,000</td>
    <td style="text-align:right">62,500,500,004</td>
    <td style="text-align:right">62,502,749,985</td>
    <td style="text-align:right">32,968,189</td>
    <td style="text-align:right">35,977,618</td></tr>
<tr><td style="text-align:right">1,000,000</td>
    <td style="text-align:right">250,001,000,004</td>
    <td style="text-align:right">250,005,499,985</td>
    <td style="text-align:right">67,979,733</td>
    <td style="text-align:right">75,964,727</td></tr>

</tbody>
</table>

.NET Framework 4.8 と .NET8.0 で比較関数の呼び出し回数を比較してみると，$n$ が小さいときは .NET 8.0 のほうが少なく，$n$ が大きくなると逆転していることが分かる。このことから，ヒープソートに切り替わる条件が両者で異なっていることが分かる。.NET Framework 4.8 のほうは $n$ に関係なく再帰関数の呼び出し深さで決まっているので，$n$ が小さいときはなかなかヒープソートに切り替わらないが，$n$ が大きくなると早めに切り替わる。一方，.NET8.0 のほうは切り替え点が $n$ の対数に比例するので両者の違いが表れている。

<!--
# 参考文献
-->

[^1]: [A Killer Adversary for Quicksort <img width=16 src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3490655/66e66c9d-a6f3-f215-951a-9d79cc94a9d6.png">](https://www.cs.dartmouth.edu/~doug/mdmspe.pdf)

[^2]: [クイックソートを攻略してみた - Zenn](https://zenn.dev/forcia_tech/articles/20230208_matsukawa)