题目重点：多篇 Infra/Exceptional SWE 面经只给整数数组多线程排序方向；明确训练 API、worker 所有权与归并成本。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 训练版输入是可放内存的整数数组和正整数 workerCount，输出升序数组；允许 O(n) 额外缓冲区，不要求稳定性。
- 使用支持真正 CPU 并行的线程运行时；若语言运行时限制纯 CPU 线程并行，收益须实测。
- 每个工作线程只写自己的不重叠区间；归并的输入区间完成后才被读取，同一层相邻归并写不重叠输出区间。
解题路线
- 把数组按连续范围均匀拆成 p=min(workerCount,n) 块，worker 在自己的块做单线程排序；用 barrier 或 futures 等待所有块完成。
- 按二路归并树逐层并行合并相邻有序块。每一层写到独立缓冲区的互不重叠范围，层完成后交换输入/输出缓冲区，直到剩一块；奇数块直接复制/保留。
- 若内存严格受限，可考虑原地归并或外部排序，但实现明显更复杂；面试中先给正确 O(n) 缓冲方案，再讨论取舍。
- 局部排序总工作 O(n log(n/p))，归并各层 O(n log p)；最终仍 O(n log n)。并行 span 依赖每层归并是否继续拆分，单线程做最后一次归并会形成 O(n) 瓶颈。
- 验证空数组、单元素、全相同、负数、p>n、非 2 的幂块数、跨块重复；比较结果与独立单线程 sort。
手动走一遍
训练数组 [9,1,8,2,7,3,6,4]、p=2：线程 A 排前半得 [1,2,8,9]，线程 B 排后半得 [3,4,6,7]；两路归并写另一缓冲区得 [1,2,3,4,6,7,8,9]。若两个线程同时写同一缓冲区起点，会发生覆盖，故输出段须预先分配唯一范围。
规模与取舍
总工作 O(n log n)、缓冲 O(n)、任务元数据 O(p)。线程启动/销毁 O(p) 额外开销，实际加速受分块大小、内存带宽与归并方式影响；小 n 应测单线程回退阈值。
易错点与追问
容易失分的边界
- 各块排序后直接拼接，结果只局部有序。
- 多个线程在同一数组重叠写，或归并读取仍在排序的块。
- 最后大归并只用一个线程，却报告理想线性加速。
- 不限制 p，给长度 8 数组启动上百线程。
- 未核运行时与内存带宽就声称 CPU 排序一定随线程数线性加速。
继续深挖
- 稳定排序怎样保持同值原有次序？
- 如何并行化最后一层大归并？
- 如果数组大到放不下内存，如何改外部归并？
- 如何选择 workerCount 与单线程回退阈值？
