一次突發奇想的「排序之罪」：如果對排序使用隨機比較器

突發奇想

今天晚上或許是太無聊了，突發奇想到：如果我在排序的時候用一個隨機函數做比較器，會發生什麼？

正常情況下，傳遞給 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] 的隨機浮點做比較器，跑三次：

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

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

看起來是一個隨機的結果，果不其然。

Python（Python 3.14.3）

使用 functools.cmp_to_key 將比較函數轉換爲 key 函數。

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

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

看起來 Python 也是給出一個隨機的結果，倒是沒有很意外。

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
})

第一次：[46, 1, 55, 20, 11, 66, 56, 88, 80, 54, 41, 77, ...]
第二次：[68, 21, 62, 78, 20, 7, 3, 16, 72, 69, 85, 36, ...]
第三次：[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;
});

第一次：[73, 3, 10, 46, 88, 72, 26, 64, 38, 75, 91, 50, ...]
第二次：[20, 76, 33, 3, 86, 47, 34, 69, 94, 24, 71, 87, ...]
第三次：[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);

第一次：[80, 57, 97, 92, 32, 3, 74, 10, 53, 35, 15, 29, ...]
第二次：[3, 27, 58, 98, 56, 28, 39, 82, 94, 53, 9, 50, ...]
第三次：[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);

第一次：[0, 3, 8, 25, 5, 27, 20, 23, 9, 32, 18, 14, ...]
第二次：[25, 79, 1, 8, 14, 17, 2, 5, 16, 9, 3, 24, ...]
第三次：[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 之前，即便比較器有缺陷，Java 也不會報錯，只會直接給出一個亂序的結果。

Rust（rustc 1.97.0）

終於到 Rust 了。AI 用了 rand::Rng 來決定 Ordering::Less 還是 Greater：

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

第一次：thread 'main' panicked at ...
第二次：thread 'main' panicked at ...
第三次：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。

於是我們自然而然地懷疑到了版本的問題，是否是因爲 Rust 版本的問題導致的？然後發現 Gork VM 中使用的 Rust 版本是 1.75.0 (82e1608df 2023-12-21)。

而我本地測試用的版本是 1.97.0 (c980f4866 2026-06-30)，我們自然而然就基本肯定了是版本的問題，不過我本來短期內也沒打算先深入研究，發佈了這篇博客的第一個版本。

而發佈出沒多久，我的一個妹妹 lfcypoopen_in_new 便在後續提供了歷史版本和具體變更的解釋。

經過她的幫助和後續研究，結論是兩個關鍵 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# 在陣列長度達到一定規模後可能拋出錯誤。

後續我將對各種語言的實際執行次數以及排序結果是否存在規律性進行分析，總之就先這樣吧，有空再折騰。