突発的な思いつき「ソートの罪」：ソートにランダムコンパレータを使ったらどうなるか

突発的な思いつき

今晩は暇すぎたのか、ふとこんなことを思いついた。もしソートのときに比較関数としてランダム関数を使ったら、何が起こるだろう？

通常、sort に渡す比較関数は a < b の真偽値を返し、どちらが前に来るかを決める。しかし、仮にランダムに返すようにしたら、ソートアルゴリズムはどのような振る舞いをするのだろうか？

また、各言語はこのような「違反」あるいは未定義動作をどのように扱うのか？ランダムな順序になるのか、それともエラーになるのか？

そこでこのリポジトリを作った：sorting-sinsopen_in_new

このプロジェクトでテストした言語は以下の通り：

• JavaScript (Node.js & Bun.js & Deno)
• Python
• Go
• C++
• C#
• Java
• Rust (latest & v1.80.0)

JavaScript、Python、Go のコードは自分で書いたが、他の言語は AI の助けを借りて書いた。

結果の予想

最初は、他の言語もランダムに近い結果を出すか、あるいはエラーを返すと思っていた。

ただ、JavaScript はランダムな結果を出すだろうし、Rust はコンパイル時にエラーになるかもしれないと考えていた。この二つの言語に対するステレオタイプ的なイメージからだ。

各言語の振る舞い

JavaScript（Node.js v24.14.0 / Bun.js 1.3.14 / Deno.js 2.9.2）

Math.random() - 0.5、つまり [-0.5, 0.5] のランダムな浮動小数点を比較関数として使い、3回実行：

arr.sort(() => Math.random() - 0.5);

1回目：[67, 68, 87, 44, 50, 16, 42, 3, 24, 31, 1, 74, ...]
2回目：[23, 69, 5, 47, 38, 36, 8, 27, 32, 11, 10, 0, ...]
3回目：[50, 15, 7, 19, 34, 31, 32, 11, 47, 48, 51, 52, ...]

ランダムな結果になっている。予想通りだ。

Python（Python 3.14.3）

functools.cmp_to_key を使って比較関数をキー関数に変換する。

arr.sort(key=cmp_to_key(lambda a, b: random.choice([-1, 0, 1])))

1回目：[79, 0, 44, 53, 38, 66, 90, 19, 3, 87, 31, 5, ...]
2回目：[0, 80, 48, 22, 30, 79, 45, 95, 70, 84, 76, 74, ...]
3回目：[17, 1, 73, 89, 80, 52, 26, 35, 30, 53, 9, 34, ...]

こちらもランダムな結果。特に驚きはない。

Go（go 1.26.2）

Go はあまり詳しくないが、なんとかコードを書いた。

sort.Slice と rand.Intn(2) == 0 を組み合わせる：

sort.Slice(arr, func(i, j int) bool {
    return rand.Intn(2) == 0
})

1回目：[46, 1, 55, 20, 11, 66, 56, 88, 80, 54, 41, 77, ...]
2回目：[68, 21, 62, 78, 20, 7, 3, 16, 72, 69, 85, 36, ...]
3回目：[26, 59, 90, 82, 20, 54, 79, 16, 43, 67, 77, 41, ...]

これもランダムな結果のようだ。

C++（clang 22.1.8）

次は C++ 版：

std::sort(arr.begin(), arr.end(), [&gen](int, int) {
    return std::uniform_int_distribution<>(0, 1)(gen) == 0;
});

1回目：[73, 3, 10, 46, 88, 72, 26, 64, 38, 75, 91, 50, ...]
2回目：[20, 76, 33, 3, 86, 47, 34, 69, 94, 24, 71, 87, ...]
3回目：[95, 1, 22, 99, 21, 94, 6, 57, 51, 85, 10, 11, ...]

C++ は非常に素直に実行され、どのような入力でも処理が進む。

C#（.NET 10.0.301）

Array.Sort(arr, (a, b) => rng.Next(2) == 0 ? -1 : 1);

1回目：[80, 57, 97, 92, 32, 3, 74, 10, 53, 35, 15, 29, ...]
2回目：[3, 27, 58, 98, 56, 28, 39, 82, 94, 53, 9, 50, ...]
3回目：[77, 19, 2, 61, 4, 15, 92, 95, 21, 7, 62, 84, ...]

しかし、配列サイズが N = 100000 に増えると、状況が変わります。

Unhandled exception. System.ArgumentException: Unable to sort because the IComparer.Compare() method returns inconsistent results. Either a value does not compare equal to itself, or one value repeatedly compared to another value yields different results. IComparer: 'System.Comparison`1[System.Int32]'.

C# は配列がある程度のサイズに達すると、比較関数の不整合を検出できます。

Java（JDK 26.0.1）

arr.sort((a, b) -> rng.nextInt(3) - 1);

1回目：[0, 3, 8, 25, 5, 27, 20, 23, 9, 32, 18, 14, ...]
2回目：[25, 79, 1, 8, 14, 17, 2, 5, 16, 9, 3, 24, ...]
3回目：[50, 12, 0, 5, 11, 1, 22, 2, 3, 19, 16, 4, ...]

C# と同様に、配列サイズが N = 100000 に増えると、状況が変わります。

Exception in thread "main" java.lang.IllegalArgumentException: Comparison method violates its general contract!

Java も配列がある程度のサイズに達すると、比較関数の問題を検出できます。

このチェックは Java 7 から導入されました。Java 7 より前では、比較関数に欠陥があってもエラーは発生せず、単に順序が乱れた結果が返されていました。

Rust（rustc 1.97.0）

いよいよ Rust だ。AI は rand::Rng を使って Ordering::Less か Greater を決めるようにした：

arr.sort_by(|_, _| {
	if rng.gen::<bool>() {
		Ordering::Less
	} else {
		Ordering::Greater
	}
});

1回目：thread 'main' panicked at ...
2回目：thread 'main' panicked at ...
3回目：thread 'main' panicked at ...

エラーメッセージ：

user-provided comparison function does not correctly implement a total order

予想の範囲内ではあるが、Rust は唯一直接 panic する言語だった（ただし、コンパイル時にエラーになるという予想は外れた）。

しかし、実行時に比較関数が total order（全順序）を実装しているかどうかを検出し、実装されていなければ即座に panic する。このように言語レベルで安全境界をチェックする姿勢は、私が持つ Rust のステレオタイプなイメージそのものだ。プログラムをクラッシュさせても、未定義動作を計算に参加させないという姿勢だ。

Rust：だが、本当にそうなのか？

Rust をテストし終えた後、友人の LaunchPadopen_in_new と共有したところ、彼が Grok で再現を試みた際には panic が発生しなかった。

これは不思議に思えた。なぜなら、私のローカル環境では確かに panic するからだ。

そこで当然のようにバージョンの問題を疑い、Grok VM で使われている Rust のバージョンが 1.75.0 (82e1608df 2023-12-21) であることを確認した。

私のローカル環境のバージョンは 1.97.0 (c980f4866 2026-06-30) だったので、ほぼ間違いなくバージョンが原因だと結論づけ、このブログ記事の初版を公開した。

公開して間もなく、妹の lfcypoopen_in_new が歴史的なバージョンと具体的な変更点についての説明を提供してくれた。

彼女の助けとその後の調査により、現在の振る舞いを形作ったのは以下の2つの重要な PR であることが分かった：

PR	PR 情報の概要	マージ日	リリースバージョン
#124032open_in_new	ソート実装を置き換え—— driftsort（slice::sort）と ipnsort（slice::sort_unstable）を導入。新実装は strict weak ordering 違反を能動的に検出して panic する。旧来の Timsort/pdqsort では検出できなかった。	2024-06-21	Rust 1.81.0
#128273open_in_new	Ord 違反のヘルプメッセージを改善—— panic メッセージを user-provided comparison function does not correctly implement a total order に最適化し、ドキュメントも改善。	2024-08-11	Rust 1.81.0

新しい実装では実行時整合性チェックが追加され、total order に違反する多くの比較関数に対して能動的に panic するようになった。一方、古いソート実装では通常そのような検出は行われない。

1.81.0 より前（例：1.80.0）では、限定的なテストにおいて非決定的な比較関数を与えても、ソートは黙ってランダムに見える順列を出力した。1.81.0 以降では、高い確率で比較関数の不一致を検出し panic する。

まとめ

言語	振る舞い
C++(Clang)	（疑似的に）ランダム順列
Python	（疑似的に）ランダム順列
JavaScript (Node.js / Bun / Deno)	（疑似的に）ランダム順列
Go	（疑似的に）ランダム順列
Java	N=100 ランダム順列、N=1,000,000 例外
C#	N=100 ランダム順列、N=1,000,000 例外
Rust(latest)	panic
Rust(v1.80.0)	（疑似的に）ランダム順列

5つの言語がランダム比較関数に対して「何事もなかったかのように振る舞う」のに対し、Rust の v1.81.0 以降だけが panic を選択し、Java と C# は配列がある程度のサイズに達するとエラーを投げる可能性がある。

今後、各言語の実際の実行回数やソート結果に規則性があるかどうかを分析する予定だ。とりあえずはここまでにして、また時間があれば続ける。