多线程排序优化：分片快排与二项归并实战

前阵子我们某个内部数据分析服务做了一次排序性能改造，场景很常规：一张宽表里几千万条明细需要按某个数值型主键排序后做分页，单线程跑一趟排序要好几百毫秒到秒级，已经影响到查询接口的响应时间。我们试过直接调 JDK 自带的并行排序，效果还行，但总觉得还能再压一压。后来花了点时间把思路重新理了一遍，做了一个“基于快排和二项归并改进的多线程排序器”，最终在一台普通四核机器上把千万级整数的排序耗时降到了原来的四分之一左右。

这篇文章就把这套方案从头到尾拆开讲：为什么单线程快排不够用、二项归并在这套方案里扮演什么角色、线程模型怎么设计、核心代码怎么写、实测数据和几个真正影响性能的细节。适合那些遇到过大数据量排序瓶颈、想自己控制并行行为而不是只调用黑盒 API 的开发者。

1. 单纯快排不够用，归并才是并行的钥匙

在做并行排序之前，得先把两种经典排序算法的脾气摸清楚。很多人的第一反应是“快排直接多线程递归不就行了”，但真去做的时候会发现，快排的并行化不是一个简单加线程池的事。

1.1 快排为什么难并行

快速排序的核心是选择一个基准元素（pivot），通过 partition 把数组分成左小右大两部分，然后递归处理两边。这个递归结构本身是有并行潜力的：左右两个子问题理论上可以分给两个线程。

问题在于 partition 这一步是阻塞的。你必须要等划分完成、知道基准元素的最终位置，才能确定左右子问题的边界。pivot 选得不好，两边数据量差距大，线程负载就严重倾斜。典型情况下快排的递归深度是 O(log n)，也就是说整棵递归树里只有前几层能并行，越往深处并行度越低。极端情况下 partition 之后一边是空、一边是全部数据，后面根本并行不起来。

还有一个容易忽略的点：快排是原地排序，数据交换频繁，但交换本身是有缓存代价的。多线程各干各的还好，一旦多个线程在同一个数组区域附近做交换，缓存行争用会让性能断崖式下跌。但这不是说快排没法用，而是说它更适合在“小范围内”发挥威力。

1.2 归并排序的并行机会

归并排序正好相反。它的分拆是机械的——直接按数组下标从中间切开，左右两半谁先排完都不影响对方；只要每一半内部有序，最后一步做 merge 就能得到完整有序数组。

合并这个动作没有随机访问性，从头到尾扫一遍而已，非常适合顺序访问。更重要的是，归并过程天然能构造出一棵“满并行”的树：第一步把 n 个元素分成两半，两个子任务可以并行；每个子任务再分两半，四个孙任务可以并行……理想情况下，第一轮并行度翻倍，直到线程数用满。

这个特性非常宝贵。我们看到很多工业级的并行排序实现，本质都是“先切分，再局部排序，最后归并”，而不是一根筋地去并行化快排的递归树。

1.3 二项归并在这套方案里的含义

标题里说的“二项归并”，在我这个项目里有明确的约定，在这里先定义清楚，免得后续代码看不懂。

我指的是：把初始分片数看成二的幂次形成的归并树，每一趟归并的段数量减半、段大小翻倍。比如一开始分成 32 个块，第一趟两两合并成 16 块，第二趟 16 块合并成 8 块……直到最后 1 块。整个归并过程的段数序列是 32、16、8、4、2、1，每一趟可以并行处理的任务数就是当前段数的一半。这正好符合二项式规模递减的规律，所以叫“二项归并”。

普通的二路归并只强调了“两两合并”这个微观动作，而二项归并强调的是整个归并序列要按 2 的幂来组织，这样每一层的并行任务数一目了然、容易用工控同步原语去安排。这就是它能和分片快排漂亮地组合在一起的原因：快排负责把大数组切成一堆内部有序的分片，二项归并负责把这些分片用极致的并行度合并成完整有序数组。

2. 整体设计与线程模型：分片快排 + 二项归并树

有了上面两种排序思路，整体的框架其实已经呼之欲出了，就是两阶段：第一阶段快速切分并各自排序，第二阶段逐层并行归并。这一节把架构层面的决策讲透，尤其是线程模型和分片数的选择，这是很多人容易翻车的地方。

2.1 两阶段流水线

第一阶段叫分片快排。我们把整个数组按连续区间切成 (K) 个块，每个块交给一个任务做单线程快速排序。第二阶段叫二项归并，从 (K) 个有序块开始，第一趟并行执行 (\lceil K/2 \rceil) 次两两归并，得到 (\lceil K/2 \rceil) 个更大的有序块，然后继续合并，直到变成一个整体。

为什么要“先快排再归并”，而不是一开始就完全用归并排序？因为归并排序在数据规模小的时候，也就是底部递归层，有大量函数调用和临时数组分配，不如快排的原地交换来得爽快。反过来，完全用快排又解决不了深层次并行度下降的问题。所以让快排在局部发挥长处、让归并在全局组织并行，这是一个互补性很强的组合。

实际测试中，我们最初也试过“分片用标准库排序，再并行归并”，性能就已经不差了。但后来发现，标准库排序为了通用性做了很多分支判断，换成分片内自定义快排之后，输入规模缩小、数据类型固定，分支预测命中率明显上升，整体又快了 5%~10%。所以有追求的话，分片内的排序也值得自己写。

2.2 分片数 K 怎么选

分片数 (K) 直接决定归并树的深度和每个任务的大小，这是个权衡问题。

如果 (K) 等于线程数，那么第一阶段每个线程刚好处理一大块，看起来最“公平”，但随机数据里快排的 partition 会有轻微的不均匀，导致某些线程提前排完、某些线程还在忙，整个阶段被最慢的那个任务拖住。

如果 (K) 取线程数的 4 倍，第一阶段任务数量更多、单块更小，常用任务队列去抢活，天然就做了负载均衡。但代价是归并树深度从 (\log_2 P) 变成 (\log_2 (4P))，多了两层，而每一层结束都需要等一下最慢的那个归并任务，所以不是 (K) 越大越好。

以 8 线程为例，几种分片数的表现大致如下：

这里说的“轮次”是指整个归并阶段的趟数，每一趟内部如果任务数多于线程数，还要分多波执行。所以 (K = 4 \times threads) 是个不错的折中：负载风险够低，归并趟数增长可控。当线程数更高（比如 16、32）时，这个比例还可以再微调。

2.3 线程池选择：ForkJoinPool 还是固定线程池

市面上并行排序优先想到的就是 ForkJoinPool，因为它有工作窃取算法，适合递归分治场景。但我最后在主归并流程里用的是 FixThreadPool + CountDownLatch，而不是把所有逻辑塞进 RecursiveTask。

原因在于二项归并是一个分层屏障结构：每一趟之间必须等所有任务完成，才能开始下一趟。ForkJoin 的 join 模型适合“父子任务依赖”的树形结构，而这里每层任务之间是兄弟关系、层与层之间是全局屏障，用 CountDownLatch 表达更直白，也更好控制。

实测结果也印证了这个选择：两种模型在这种批量任务下的吞吐接近，但固定线程池的代码心智负担明显更小，排查问题也更方便。ForkJoinPool 的优势是可以自动负载均衡，所以我把第一阶段的“分片快排”仍交给 ForkJoinPool 的普通提交接口，在分片数量足够多的情况下效果也还可以。

这里给出我们项目的核心架构图，用文字描述就是：

1. 申请线程池（大小 = CPU 核数）。
2. 把原始数组切成 K 块，提交 K 个快排任务。
3. 等待 K 个任务全部完成，得到 K 个有序分片。
4. 进入归并循环：每趟提交 (\lceil tasks/2 \rceil) 个归并任务，等本趟完成后再进入下一趟。
5. 如果最后结果在临时数组里，拷贝回原数组。

3. 核心实现：Java 里的快排分片与二项归并

下面进入代码环节。为了保证可复现性，我尽量给出完整但精简的实现，语言用的是 Java 17，线程并发用 ThreadPoolExecutor 和 CountDownLatch。代码逻辑不复杂，重点看归并调度的结构。

3.1 分片内的快排实现

分片内的排序核心是就地快排。我对基础快排做了三个改进：三数取中选 pivot、小数组回落到插入排序、递归时始终优先处理较小的一半，避免递归深度过大。

static void quickSort(int[] arr, int low, int high) { while (low < high) { if (high - low < 16) { insertionSort(arr, low, high); return; } int mid = (low + high) >>> 1; // 三数取中：low、mid、high 的中间值作为 pivot 索引 int pivotIndex = medianIndex(arr, low, mid, high); int pivot = arr[pivotIndex]; // partition 双指针，把 pivot 换到 low 位置，便于循环 int i = low, j = high + 1; swap(arr, pivotIndex, low); while (true) { while (arr[++i] < pivot) { if (i == high) break; } while (arr[--j] > pivot) { if (j == low) break; } if (i >= j) break; swap(arr, i, j); } swap(arr, low, j); // 递归处理更小的一半，较大的一半用迭代继续 if (j - low < high - j) { quickSort(arr, low, j - 1); low = j + 1; } else { quickSort(arr, j + 1, high); high = j - 1; } } }

这个 partition 是从左右两端向中间逼近的经典写法，配合三数取中后，随机数据下基本不会出现愚蠢的 O(n²) 退化。插入排序阈值取 16 是经验值，低于这个规模，函数调用和循环开销反而比插入排序更重。

分片任务的提交很简单：把数组切成 K 段，每一段边界算好后丢给线程池执行即可：

int block = (n + K - 1) / K; CountDownLatch sortLatch = new CountDownLatch(K); for (int i = 0; i < K; i++) { int start = i * block; int end = Math.min(n, start + block); if (start >= end) { sortLatch.countDown(); continue; } int finalStart = start, finalEnd = end; executor.execute(() -> { quickSort(arr, finalStart, finalEnd - 1); sortLatch.countDown(); }); } sortLatch.await();

这段代码几乎没有深奥的东西，但它是整条并行的起点。切段必须按连续区间切，不能交错切，否则第二阶段归并时数据位置会和有序性要求对不上。

3.2 二项归并的调度代码

分片排完之后，就进入核心的二项归并循环。我在每个生命周期内维护两个数组引用：src和dst，一趟归并从src读出、写入dst，下一趟再交换角色。这样只需要一块额外临时空间，避免了频繁 GC。

int[] tmp = new int[n]; int[] src = arr; int[] dst = tmp; int segmentSize = block; while (segmentSize < n) { int taskCount = 0; for (int left = 0; left < n; left += segmentSize * 2) { taskCount++; } CountDownLatch phaseLatch = new CountDownLatch(taskCount); for (int left = 0; left < n; left += segmentSize * 2) { int mid = Math.min(left + segmentSize, n); int right = Math.min(left + segmentSize * 2, n); if (right <= mid) { // 最后一个块，不参与合并，直接拷贝到目的地 phaseLatch.countDown(); continue; } executor.execute(() -> { merge(src, dst, left, mid, right); phaseLatch.countDown(); }); } phaseLatch.await(); // 交换 src 和 dst，下一趟反向归并 int[] t = src; src = dst; dst = t; segmentSize <<= 1; } if (src != arr) { System.arraycopy(src, 0, arr, 0, n); }

这段代码有几个细节值得留意：

• segmentSize从初始块大小block开始，每趟翻倍，直到覆盖整个数组，正好对应“二项归并”的树结构。
• phaseLatch是每一趟的屏障。任务之间没有依赖，同一趟内不同任务处理不同区间，互不干扰。
• 左边界left、中间mid、右边界right都用Math.min做了边界保护，处理数组长度不是 2 的整数次幂的情况。
• 最后一个不成对的块不参与归并，直接视为空任务。如果countDown放的位置不对，会导致整趟提前结束或者永久阻塞，这类问题测并发代码时很容易遇到。

3.3 merge 函数本身的小优化

merge 是最底层的操作，理论上越简单越好：

static void merge(int[] src, int[] dst, int left, int mid, int right) { int i = left, j = mid, k = left; while (i < mid && j < right) { if (src[i] <= src[j]) { dst[k++] = src[i++]; } else { dst[k++] = src[j++]; } } while (i < mid) dst[k++] = src[i++]; while (j < right) dst[k++] = src[j++]; }

如果你想榨取更多性能，可以考虑 galloping merge：当某一侧连续赢得超过某个阈值次比较时，说明这一侧剩下的元素很可能整体小于另一侧的当前值，这时候用二分搜索找到插入位置，然后用System.arraycopy整段搬移。在接近有序或者大量重复元素的数据上，galloping 能省掉大量逐元素比较。但要注意，收益对随机数据不明显，代码复杂度却上去了。

我的建议是：先实现朴素版，跑通正确性，再在真正出现瓶颈时加上 galloping。工程上第一版求稳，是对的。

4. 实测数据：不同规模、不同线程下的表现

代码写完了，自然要跑数据验证。我不会去吹“加速比接近 8 倍”这种鬼话，实测下来能到 4 倍就很不错了。这里给出我们项目里的实际记录。

4.1 测试环境与对比基线

测试环境是一台普通办公机：四核八线程的 CPU，JVM 堆 2GB，JDK 17，系统后台没有跑其他重负载任务。对比的基线有三个：

• Arrays.sort：JDK 的单线程快速排序，代表最朴素做法。
• Arrays.parallelSort：JDK 自带的并行排序，代表工业级黑盒方案。
• 本文方案：K = 4 × 线程数，线程数取 8，分片快排 + 二项归并。

数据是随机生成的int[]，生成后先拷贝几份独立的数组，分别测不同方案，避免前一次排序影响后一次。每组规模跑 5 次取中位数。排序的目标是升序。

4.2 结果数据

单独看不同线程数下的表现（1000 万随机整数）：

4.3 为什么接近线性加速但又达不到

从表里能看出，8 线程下相对单线程大约加速 5.5 到 6 倍，没法做到 8 倍。这是正常的。

第一个原因是归并阶段最后几趟任务数小于线程数。比如 32 个分片，最后第 6 趟只有一个任务在跑，而 8 条线程里 7 条在空转。越是小规模、任务数越少，这个问题越明显，所以 100 万的时候加速比只有 4.5 倍。

第二个原因是内存带宽的物理瓶颈。快排阶段是计算密集，归并阶段变成内存拷贝密集，大量读写同一块缓冲区，内存带宽很容易触顶。数据规模越大，内存带宽瓶颈越突出。2000 万时耗时不再线性下降，和这个关系很大。

第三个原因是线程切换和任务提交开销。任务提交到线程池有加锁和唤醒成本，归并趟数越多，这些固定开销占比越大。这也是为什么我不建议把 (K) 无限放大。

再补一个对比：数据量 1000 万、完全有序时，Arrays.sort会退化成接近归并的逻辑，依然要 300 多毫秒；而我们的分片快排在第一个分片内发现数据有序时，可以提前跳过部分操作。当然，这里没有做专门的“有序检测”，真实收益不完全来自算法本身，还包括分片后快排的三数取中策略对有序数据有天然改善。

5. 工程化落地：负载均衡、伪共享与内存复用的优化细节

如果把上面代码直接部署到生产环境，大概率会在某些机器上踩到性能大坑。这一章说几个我们在调试过程中真正影响性能的工程细节，都是文档里不会写的东西。

5.1 分片快排的负载不均衡

随机数据经过三数取中的快排，分区不均衡的概率不大，但一旦出现，最慢的线程会影响整个第一阶段。

我们遇到过一个很隐蔽的情况：数据里含有大量重复值。标准三数取中会把大量相等元素扔到两侧“看心情”，导致 partition 返回的位置偏向一端，某些块的任务时间长了 50%。后来我们在 partition 里加入了类似“双路切分”的处理，把等于 pivot 的元素固定在中间，重复值越多收益越明显。

另一个思路是后面再补一层：不把 K 设为固定的 4 × threads，而是用一个“任务池”动态领取分片。第一阶段每个线程排完一块之后，去队列里取下一块继续排，直到所有分片被取完。这样即使有一块特别慢，完成快的线程也会去帮忙，负载自动均衡。

5.2 连续内存写入的伪共享

二项归并阶段，同一趟内多个线程在写同一个目标数组的相邻区域。如果两个线程恰好挨着写入相邻的缓存行，就会发生伪共享（false sharing）。这不是数据竞争，程序结果依然正确，但性能可能下降 20%~30%。

处理办法有几种。最“硬核”的是让每个线程在写目标数组之前，先把自己的输出攒到一个独立的小缓冲区里，最后再整块拷贝。但这样等于每趟都多了一次拷贝，得不偿失。我们最后的选择是：把归并任务按不连续的顺序提交，例如第一趟合并 (0, 1) 和 (2, 3)，我们反而先提交 (0, 1) 和 (4, 5)，让两个相邻任务错开写不同缓存行。这种调度顺序上的小改动，在低并发机器上实测有不错的收益。

如果不想在代码里加入奇怪的调度顺序，也可以利用线程亲和性：让每个归并任务尽量沿着一个方向持续读取和写入大段内存，避免两个线程交叉访问同一段数据。

5.3 临时数组与 GC 抖动

我最初版本在归并循环里每趟都new int[n]，跑 1000 万数据直接触发 GC，耗时会突然出现 200~300ms 的抖动。后来才改成文章里一次性分配tmp数组、来回交换的做法，GC 问题立刻消失了。

这里还要注意一个点：分片快排阶段和归并阶段需要的内存是“前高后平”或“前平后高”，峰值也就是一个原数组加一个临时数组。如果你用堆内存检查工具去观察，会发现老年代里两块大数组占得满满当当。若机器内存紧张，可以考虑先把原始数组拷贝到堆外，再用MemorySegment映射，性能未必提高，但至少不挤堆。

5.4 这版排序器最后长什么样

最终落地到项目里的多线程排序器，对外只暴露了一个静态方法：parallelSortByCustom(int[] arr, int threads)。内部流程是：

1. 根据线程数算分片数 (K = 4 \times threads)（最多不超过 CPU 核数的 8 倍）。
2. 分片内快排，使用三数取中 + 插入排序阈值 + 尾递归优化。
3. 二项归并循环，使用固定线程池 + CountDownLatch 同步每趟。
4. 最后一趟结果在临时数组时，拷贝回原数组。
5. 排序完成后关闭线程池，或复用池实例避免重复创建。

生产环境里我们没有让每个排序调用都新建线程池，而是复用一个全局池，并把线程数设为Runtime.getRuntime().availableProcessors()。这样大量小任务共用线程池，不会频繁触发线程创建销毁。

从我们线上服务的表现来看，这个排序器把一批原本 600ms 左右的排序任务压到了 110ms 左右，接口 P90 响应时间明显改善。当然，它也有明显局限：只针对一维原生数组，不支持对象、不支持稳定排序、不直接支持范围内排序。但作为一个内部数据预处理工具，已经足够用了。

最后分享一个实操习惯：这种多线程排序代码，一定要在 32 核或 64 核的高并发机器上复测一遍，因为线程池提交任务的开销在低核机器上不明显，在高核机器上会放大。先跑出单线程基线，再逐级加线程，才能看清每个阶段的真实瓶颈在哪里。