并行排序

主线位置：主线 1 的直接用户。par_sort / par_sort_unstable 不走并行迭代器的切分器（只有 par_sort 的第一步借了一下 par_chunks_mut），而是在排序算法的递归里自己调 rayon_core::join：每次 join 就是一次 join 与 join_context。

flowchart TB
  ps["par_sort()：par_mergesort"] --> m1{"len"}
  m1 -->|"≤ 20"| ins["插入排序，不分配"]
  m1 -->|"≤ 2000"| seq["分配 len 个元素的缓冲；顺序 merge_sort（类 TimSort）"]
  m1 -->|"> 2000"| chunks["par_chunks_mut(2000).with_max_len(1)：每块顺序 merge_sort"]
  chunks --> cat["调用线程上：相邻的未改动 run 拼起来"]
  cat --> mr["merge_recurse：join 两半，再 par_merge"]
  mr --> pm{"两边总长 ≥ 5000？"}
  pm -->|是| sfm["split_for_merge 二分找切点，join 两半"]
  pm -->|否| sm["顺序归并"]
  pu["par_sort_unstable()：par_quicksort"] --> rec["recurse：pdqsort 选主元、分区"]
  rec --> q{"分区后两边都 ≤ 2000？"}
  q -->|是| tail["顺序：短的一边递归，长的一边循环"]
  q -->|否| jn["join(左 recurse, 右 recurse)"]

抄自 std 的哪一版

src/slice/sort.rs 1686 行，文件头注释：

//! **Parallel** Slice sorting
//!
//! This implementation is mostly copied from the `core::slice::sort` module, with minimal changes
//! to support stable Rust and parallel `is_less` (e.g. `Fn` rather than `FnMut`).
//!
//! ---
//!
//! This module contains a sorting algorithm based on ... pattern-defeating quicksort, ...
//!
//! Unstable sorting is compatible with core because it doesn't allocate memory, unlike our
//! stable sorting implementation.
//!
//! In addition it also contains the core logic of the stable sort used by `slice::sort` based on
//! TimSort.

（算法作者名和链接略。）「---」以下那一段，和 std 换算法之前的 core/src/slice/sort.rs 文件头逐字相同。这个文件是 59db658「Sync par_sort* with the standard library」（2024-04-04，#1156）建立的，提交说明是：rayon 的并行排序本来就基于 std，但已经过时；std 那时把大部分实现搬进了统一的 core::slice::sort 模块，这次把 rayon 也换成基于它的统一 sort.rs，并行化的部分和以前一样。git tag --contains 显示这个提交第一次出现在 rayon 1.11.0（2025-08-12），那一版的发布说明没有提它。

本机 rustc 1.99.1 的 std 已经不是这套算法了。rust-src 里 core/src/slice/sort/ 是一个目录：

• stable/mod.rs:22：「Stable sort called driftsort」，入口在小于等于 20 个元素时插入排序，否则 driftsort_main，driftsort_main 里有一块 4 KiB 的栈上 scratch，小输入不调分配器（同文件 94-137 行，栈缓冲在 121 行）。
• unstable/mod.rs:15：「Unstable sort called ipnsort」。

而 rayon v1.12.0 的 sort.rs 里是 partition_in_blocks / choose_pivot / break_patterns / heapsort（pdqsort）和带 TimSortRun 栈、collapse 规则的 merge_sort。拿本机一份 Rust 1.75 时期的 core/src/slice/sort.rs（另一个工具链附带的 rust-src）和它逐函数 diff：partition_in_blocks 的差别只有 FnMut → Fn、mem::size_of → size_of、addr() → as usize、MaybeUninit::slice_as_mut_ptr → as_mut_ptr() as *mut u8 这几行。所以页面上的结论是：rayon 保留的是 std 换成 driftsort / ipnsort 之前的那套算法（不稳定排序是 pdqsort，稳定排序是类 TimSort 的归并），只把 FnMut 改成 Fn + Sync，再在三个地方插入 join。std 是在哪个版本换的算法，本机没有可引用的出处，这里不写。

par_sort / par_sort_by / par_sort_by_key 都调 par_mergesort，par_sort_unstable* 都调 par_quicksort（slice/mod.rs:392-396、631-635）。比较函数统一成 is_less: Fn(&T, &T) -> bool + Sync，par_sort 传的是 T::lt。

par_sort_unstable：pdqsort 加一个 join

recurse 就是 pdqsort 的主循环：≤ 20 个元素插入排序；坏主元太多退回 heapsort；choose_pivot 选主元并猜是否已排序；猜「已排序」就先试 partial_insertion_sort；主元等于前驱时用 partition_equal 处理大量重复；否则 partition。和 std 旧版唯一的区别在分区之后：

// If both partitions are up to this length, we continue sequentially. This number is as small
// as possible but so that the overhead of Rayon's task scheduling is still negligible.
const MAX_SEQUENTIAL: usize = 2000;

// ...
if Ord::max(left.len(), right.len()) <= MAX_SEQUENTIAL {
    // Recurse into the shorter side only in order to minimize the total number of recursive
    // calls and consume less stack space. Then just continue with the longer side (this is
    // akin to tail recursion).
    if left.len() < right.len() {
        recurse(left, is_less, pred, limit);
        v = right;
        pred = Some(pivot);
    } else {
        recurse(right, is_less, Some(pivot), limit);
        v = left;
    }
} else {
    // Sort the left and right half in parallel.
    rayon_core::join(
        || recurse(left, is_less, pred, limit),
        || recurse(right, is_less, Some(pivot), limit),
    );
    break;
}

（sort.rs:907-927。）两边都不超过 2000 就照 std 的写法顺序做；任一边超过 2000 就 join 两边。不分配内存，这也是文件头说「unstable sorting is compatible with core」的原因。

结构上的含义：第一次分区在调用线程上，对整个数组顺序地做。n 个元素的第一次 partition 要比较约 n 次，之后两半才并行；第二层两次分区各 n/2，依此类推。关键路径上的分区工作是 n + n/2 + n/4 + … ≈ 2n 次比较，而总工作量是 n·log₂n 量级，所以单纯按比较次数算，并行度上限大约是 log₂n / 2（10⁷ 时约 11.6）。这是按代码结构的估算，没有考虑内存带宽；E9 实测下面给出。

par_sort：先分块，再并行归并

par_mergesort 分四段：

1. ≤ 20 个元素：插入排序，不分配。
2. 分配缓冲：Vec::<T>::with_capacity(len)，长度保持 0，只用它的内存做浅拷贝的落脚处（注释：这样 is_less panic 时不会对拷贝出来的副本跑析构）。所以 par_sort 需要和输入等长的额外内存。
3. ≤ 2000 个元素：直接顺序 merge_sort，返回。不进线程池。
4. > 2000 个元素：

v.par_chunks_mut(CHUNK_LENGTH)
    .with_max_len(1)
    .enumerate()
    .map(move |(i, chunk)| {
        let l = CHUNK_LENGTH * i;
        let r = l + chunk.len();
        unsafe {
            let buf = buf.get().add(l);
            (l, r, merge_sort(chunk, buf, is_less))
        }
    })
    .collect::<Vec<_>>()

用并行迭代器把数组切成 2000 个一块，每块各自顺序 merge_sort。with_max_len(1) 让切分器至少切到每片一块（bridge 与自适应切分），collect 走的是就地写入（collect 到 Vec）。每块返回 MergeSortResult：NonDescending（本来就有序，没动）、Descending（本来就严格降序，没动）、Sorted（排过了）。

然后在调用线程上扫一遍结果，把相邻的、同为 NonDescending 或同为 Descending 且衔接处也满足顺序的块拼成一个 run，降序的 run 原地 reverse。已排序的输入在这一步就几乎完成了，所有块被拼成一个 run，不需要归并。

最后 merge_recurse 对 run 列表二分：join 递归排好左右两半（结果在 v 和 buf 之间交替存放，into_buf 每层取反），回来后 par_merge 把两半归并。par_merge 在两边总长 < 5000 时顺序归并；否则 split_for_merge 取较长一边的中点，在另一边二分查找对应位置，把一次大归并拆成两次互不相干的小归并，再 join。归并本身也被并行化了，所以和快排不同，par_sort 的关键路径上没有一整遍 O(n) 的顺序扫描（除了第 4 步那次 O(块数) 的拼接）。

panic 安全靠两个守卫：par_merge 的 State 和 merge_recurse 的 MergeHole，析构时把还没归并的元素原样拷回目标位置，保证 is_less 中途 panic 时每个元素恰好出现一次。

par_sort_by_cached_key(f) 不走归并：先 par_iter_mut().enumerate().map(|(i, x)| (f(x), i)).collect() 算出所有键（下标用能装下 len 的最小整数类型），对 (键, 下标) 做 par_sort_unstable（下标唯一，所以不稳定排序也是稳定的），再顺序地按下标链把原切片原地换到位（slice/mod.rs:548-596）。

实验 E9：加速比与「小 n 为什么慢」

exp-rayon/par-sort/。随机 u64（固定种子的 xorshift），每种排序 5 次取中位数，每次排序前从同一份原数据复制；12 线程全局池，排序前 broadcast 预热；「1 线程」是在 num_threads(1) 的池里 install 调用。测前 1 分钟 / 5 分钟负载 1.69 / 2.96（测完 1.97 / 2.98）。单位 ms，括号里是 std / rayon（大于 1 表示 rayon 快）：

（10³、10⁴ 的「1 线程」一栏没有列：那一栏包含一次 install 进池再出来的固定开销，n 小时这部分占大头，不反映排序本身。此前另有两轮在 5 分钟负载很高、正在回落时测过，各格的比值和上表同量级，不再列出。）

已排序的 10⁷：sort 3.0 ms，par_sort 0.9 ms，sort_unstable 3.0 ms，par_sort_unstable 4.2 ms。逆序的 10⁷：sort 4.4 ms，par_sort 4.4 ms。

另一组不计时的测量（par_sort where）：用一个计数的比较函数调 *_by，统计比较发生在调用线程（main）上还是 worker 上：

                             n   调用线程上的比较   worker 上的比较
std sort_by               1000        10879              0
rayon par_sort_by         1000         9737              0
std sort_unstable_by      1000        10377              0
rayon par_sort_unstable_by 1000        11062              0
rayon par_sort_by         2000        21419              0
rayon par_sort_by         2001         1299          21419
rayon par_sort_unstable_by 2001        23788              0
rayon par_sort_unstable_by 4000         4013          50929
rayon par_sort_by       100000           16        1644976
rayon par_sort_unstable_by 100000      100013        1774372
rayon par_sort_by      1000000           19       19711901
rayon par_sort_unstable_by 1000000    1000013       20958471

读这两张表：

小 n 根本没进线程池。 n ≤ 2000 时两种并行排序的比较全部发生在调用线程上，worker 上是 0：par_sort 走第 3 段的顺序 merge_sort，par_sort_unstable 每次分区后两边都 ≤ 2000，从不 join。所以 10³ 时 par_sort 慢 3 倍多、par_sort_unstable 慢 1.6 倍，和并行调度没有关系，比的是 rayon 保留的旧算法和 std 现在的新算法。而且 n = 1000 时 rayon 的归并排序比 std 少比较 10%（9737 对 10879），时间却多 3 倍，差距不在比较次数上（推测在小规模排序的实现方式和缓冲分配上：std 新版有 4 KiB 栈上 scratch，rayon 每次 Vec::with_capacity(len)；本页没有进一步拆分验证）。

1 线程把并行和算法分开。 在 1 线程池里，par_sort 在各个 n 上都只有 std sort 的 0.28–0.31 倍，par_sort_unstable 是 sort_unstable 的 0.48–0.52 倍。这是 rayon 的顺序基线比 std 慢 2–3.5 倍；join 在 1 线程时的开销很小（join 一章 E1：每次约 6.6 ns），解释不了这个差距。

12 线程相对自己的 1 线程： 10⁷ 时 par_sort 632 → 67 ms（约 9.5 倍），par_sort_unstable 246 → 37 ms（约 6.7 倍）。并行化本身是有效的；对 std 只剩约 3 倍，是因为起点慢了 2–3 倍。

快排的顺序部分看得见。 par_sort_unstable 在 n = 10⁵、10⁶ 时调用线程上恰好比较了 n + 13 次：就是第一次分区（加上选主元），在 main 上对整个数组顺序完成，其余才分给 worker。par_sort 在 main 上只有 16–19 次比较，是顶层 par_merge 的 split_for_merge 二分查找，其余全部在 worker 上。这和它们的自我加速比（9.5 倍对 6.7 倍）方向一致。n = 2001 是两者的分界示例：归并排序切出两块就进了池，而快排第一次分区后两边都不超过 2000，全程留在调用线程。

已排序输入。 par_sort 0.9 ms，比 sort 快 3 倍多：每块 merge_sort 发现自己 NonDescending，拼接后只剩一个 run，没有归并。par_sort_unstable 反而比 sort_unstable 慢（4.2 对 3.0 ms）：choose_pivot 猜到「可能已排序」，在调用线程上对整个数组跑 partial_insertion_sort，这一遍是顺序的，12 个线程帮不上忙。

反向验证：1 线程下 par_sort 不应比 sort 慢「太多」——计划的预期（只多缓冲和分块开销）不成立，实测慢 3 倍多；原因是上面说的算法版本差异，不是缓冲和分块。

什么时候用

• 10⁵ 以下（u64 这类廉价比较）：直接 std 的 sort / sort_unstable。2000 以下 rayon 甚至不并行，只是换了一个更慢的顺序算法。
• 10⁶ 以上：par_sort_unstable 约 3 倍于 sort_unstable、par_sort 2–3 倍于 sort（本机 12 线程）。要稳定排序且内存紧张时注意 par_sort 的 n 个元素额外缓冲（std 的 driftsort 对大输入用 n/2）。
• 比较函数很贵（比如按字符串比较、调用闭包算键）时，排序算法本身的差距被比较开销稀释，并行的收益会更大；这一点本页没有实测，属推测。键计算贵时用 par_sort_by_cached_key，键只算一次且是并行算的。

小结

• sort.rs 文件头说「mostly copied from core::slice::sort」，对照本机 std 1.99.1 的 slice/sort/（driftsort / ipnsort）和一份旧版 core 源码核实：rayon 保留的是 std 换算法之前的类 TimSort 归并与 pdqsort，同步于 2024 年的 #1156（随 1.11.0 发布）。
• par_sort_unstable：pdqsort 分区后任一边 > 2000 就 join 两边，不分配；第一次分区在调用线程上顺序完成。
• par_sort：≤ 2000 顺序；否则 par_chunks_mut(2000).with_max_len(1) 各块排序，拼接已有序的 run，merge_recurse + par_merge（≥ 5000 时二分切开再 join）；需要 n 个元素的缓冲。
• E9：10⁷ 个 u64 约 3.0 倍（稳定）/ 3.5 倍（不稳定）于 std；相对自己的 1 线程是 9.5 / 6.7 倍；1 线程时只有 std 的 0.3 / 0.5 倍。
• n ≤ 2000 时比较全部在调用线程上，不进池，慢 1.6–3.3 倍完全来自顺序算法；小 n 慢不是调度开销。