Rust 中 Rayon 并行快速排序为何优于归并排序？适用场景与取舍分析

核心原因：并行化效率差异

快速排序的天然并行性

分治独立性：快速排序的每轮分区（partition）会将数据分为左右两部分，左右子任务完全独立，适合 Rayon 的 par_iter 并行分治。
原地操作：无需额外内存，并行任务间的缓存局部性更好。
负载均衡：Rayon 的工作窃取（Work Stealing）机制能动态分配不均匀的分区任务（如分区后的左右大小差异）。

use rayon::prelude::*;
fn parallel_quicksort<T: Send + Ord>(arr: &mut [T]) {
    if arr.len() <= 1 { return; }
    let pivot = partition(arr); // 分区逻辑
    let (left, right) = arr.split_at_mut(pivot);
    rayon::join(|| parallel_quicksort(left),
                || parallel_quicksort(right));
}

归并排序的并行瓶颈
- 合并阶段串行化：归并排序的最终合并（merge）需要严格顺序处理，难以有效并行化（需跨线程同步合并指针）。
- 内存开销：归并排序需要额外内存空间（O(n)），并行化时多线程的内存分配可能成为瓶颈。

何时选择归并排序？

稳定性需求
- 归并排序是稳定排序（相等元素顺序不变），而快速排序不稳定。
- 若业务逻辑依赖稳定性（如按多字段排序），需选择稳定算法。
数据特性适配
- 近乎有序的数据：归并排序对部分有序数据更高效（合并阶段减少比较）。
- 内存充足场景：若可接受 O(n) 额外内存，归并排序能保证最坏 O(n log n) 时间复杂度（快速排序最坏 O(n²)）。
单线程环境
- 标准库的 sort（稳定）和 sort_unstable（快速排序变种）在单线程下可能更优，避免并行调度开销。

Rayon 的实践选择

par_sort_unstable：基于并行快速排序，默认推荐（牺牲稳定性换取速度和低内存）。
par_sort：稳定排序，内部可能结合归并和插入排序，适合需要稳定性的场景。

性能对比示例

use rayon::prelude::*;
use rand::Rng;

let mut data: Vec<u32> = rand::thread_rng().gen_iter().take(10_000_000).collect();

// 并行快速排序（不稳定）
data.par_sort_unstable(); 

// 并行归并排序（稳定）
data.par_sort();

场景	快速排序优势	归并排序优势
大规模随机数据	✅ 并行效率高，内存低	❌ 合并阶段慢
小规模数据	❌ 并行开销大	✅ 单线程更优
需要稳定性	❌ 无法保证	✅ 必须选择
数据部分有序	❌ 分区可能不均匀	✅ 合并阶段高效

总结

选择快速排序：追求极致速度、可接受不稳定、数据量大且随机。
选择归并排序：需稳定性、数据部分有序、或规避快速排序的最坏情况。
Rayon 的优化：通过 par_sort_unstable 和 par_sort 封装了底层差异，根据需求一键选择。