归并排序之所以高效，关键在于一个基础操作：把两个有序数组合并成一个更大的有序数组。这个操作看似简单，却是整个归并排序算法的核心，同时也是外部排序（比如对超出内存容量的海量数据进行排序）的基石。本文将围绕 Java 数组，手把手实现有序数组合并，并逐步扩展到支持大规模排序的多路归并方案。
一、双指针合并：最基础的归并实现
假设有两个已经升序排列的整数数组 a 和 b，目标是把它们合并成一个新的升序数组。最直观的思路是使用两个指针 i 和 j 分别指向 a 和 b 的起始位置，每次比较两个指针所指的元素，把较小的放入结果数组，并移动对应的指针。当一个数组被遍历完后，另一个数组剩余的部分直接追加到结果末尾即可。
下面是完整的 Java 实现：
public class MergeDemo {
/**
* 将两个升序数组合并为一个新的升序数组
*/
public static int[] merge(int[] a, int[] b) {
int[] result = new int[a.length + b.length];
int i = 0, j = 0, k = 0;
// 双指针比较，每次取较小的元素放入结果数组
while (i < a.length && j < b.length) {
if (a[i] <= b[j]) {
result[k++] = a[i++];
} else {
result[k++] = b[j++];
}
}
// 处理 a 数组的剩余部分
while (i < a.length) {
result[k++] = a[i++];
}
// 处理 b 数组的剩余部分
while (j < b.length) {
result[k++] = b[j++];
}
return result;
}
public static void main(String[] args) {
int[] a = {1, 3, 5, 7, 9};
int[] b = {2, 4, 6, 8, 10, 12};
int[] merged = merge(a, b);
System.out.println(java.util.Arrays.toString(merged));
// 输出: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12]
}
}
这段代码有几个值得注意的细节。第一，比较时使用 <= 而不是 <，这样当两个元素相等时优先取 a 数组的元素，可以保证合并的稳定性。稳定性对于排序算法非常重要，尤其在排序对象包含多个字段时，稳定的排序能保留原有的相对顺序。第二，两个收尾的 while 循环看起来重复，但缺一不可，因为任意一个数组都可能先被耗尽，而另一个数组剩下的部分本身就是有序的，直接整体复制即可。
从时间复杂度来看，每个元素恰好被访问一次，因此合并操作的时间复杂度是 O(m+n)，其中 m 和 n 是两个数组的长度。空间上需要一个额外的结果数组，复杂度同样是 O(m+n)。这种线性复杂度正是归并算法高效的根本原因。
二、原地归并与递归归并排序
上面的实现简单清晰，但每次合并都要开辟新数组。在实现完整的归并排序时，通常采用另一种写法：预先分配一个辅助数组，通过传入下标范围在原数组上进行合并，避免反复创建对象。这就是所谓的原地归并（借助辅助空间，但复用同一块内存）。
public class MergeSort {
private static int[] temp; // 复用的辅助数组
public static void sort(int[] arr) {
temp = new int[arr.length];
mergeSort(arr, 0, arr.length - 1);
}
private static void mergeSort(int[] arr, int left, int right) {
if (left >= right) {
return; // 只剩一个元素，天然有序
}
int mid = left + (right - left) / 2; // 防止溢出的写法
mergeSort(arr, left, mid); // 排序左半部分
mergeSort(arr, mid + 1, right); // 排序右半部分
merge(arr, left, mid, right); // 合并两个有序段
}
private static void merge(int[] arr, int left, int mid, int right) {
// 把 [left, right] 区间复制到辅助数组
for (int i = left; i <= right; i++) {
temp[i] = arr[i];
}
int i = left, j = mid + 1;
for (int k = left; k <= right; k++) {
if (i > mid) {
arr[k] = temp[j++]; // 左半部分已用完
} else if (j > right) {
arr[k] = temp[i++]; // 右半部分已用完
} else if (temp[i] <= temp[j]) {
arr[k] = temp[i++]; // 取较小者，保证稳定性
} else {
arr[k] = temp[j++];
}
}
}
public static void main(String[] args) {
int[] data = {38, 27, 43, 3, 9, 82, 10};
sort(data);
System.out.println(java.util.Arrays.toString(data));
// 输出: [3, 9, 10, 27, 38, 43, 82]
}
}
注意计算中点时使用 left + (right - left) / 2 而不是 (left + right) / 2，后者在数组非常大时可能出现 int 溢出，导致 mid 变成负数，进而抛出数组越界异常。这是归并排序中一个非常经典的隐蔽 bug，面试和实际开发中都经常出现。
归并排序整体的时间复杂度是 O(n log n)，且最好、最坏、平均情况都是如此，非常稳定。它不受输入数据初始顺序的影响，这一点比快速排序更可靠。缺点是需要 O(n) 的额外空间，在内存极其紧张的场景下需要权衡。
三、多路归并：支持大规模数据排序
当数据规模大到内存放不下时，比如要对几十 GB 的日志文件排序，就不能简单地把所有数据读进内存了。常见做法是外部排序：先把大文件切分成若干个能放进内存的小块，分别用普通排序算法排好序写入临时文件，这些有序的小文件称为归并段；然后用多路归并把所有归并段合并成最终的大文件。
两两归并虽然可行，但效率不高。更优的方案是使用小顶堆（Java 中可以用 PriorityQueue）一次归并 k 路。基本思路是：每个归并段维护一个当前指针，把各路的当前元素放进小顶堆，每次取出堆顶（即当前全局最小值）写入结果，然后从该元素所属的归并段补充下一个元素进堆。这样每次取最小值的代价只有 O(log k)，总复杂度为 O(n log k)，其中 n 是总元素数，k 是归并段数量。
import java.util.PriorityQueue;
public class KWayMerge {
// 堆中的节点：记录值以及它来自哪一路、当前位置
static class Node implements Comparable<Node> {
int value;
int sourceIndex; // 来自第几个归并段
int pos; // 在该归并段中的下标
Node(int value, int sourceIndex, int pos) {
this.value = value;
this.sourceIndex = sourceIndex;
this.pos = pos;
}
@Override
public int compareTo(Node other) {
return Integer.compare(this.value, other.value);
}
}
public static int[] mergeK(int[][] segments) {
int total = 0;
for (int[] seg : segments) {
total += seg.length;
}
int[] result = new int[total];
PriorityQueue<Node> heap = new PriorityQueue<>();
// 初始化：每一路的第一个元素入堆
for (int i = 0; i < segments.length; i++) {
if (segments[i].length > 0) {
heap.offer(new Node(segments[i][0], i, 0));
}
}
int k = 0;
while (!heap.isEmpty()) {
Node node = heap.poll();
result[k++] = node.value;
int nextPos = node.pos + 1;
int[] seg = segments[node.sourceIndex];
if (nextPos < seg.length) {
heap.offer(new Node(seg[nextPos], node.sourceIndex, nextPos));
}
}
return result;
}
public static void main(String[] args) {
int[][] segments = {
{1, 5, 9},
{2, 4, 12},
{3, 8, 10, 15}
};
int[] merged = mergeK(segments);
System.out.println(java.util.Arrays.toString(merged));
// 输出: [1, 2, 3, 4, 5, 8, 9, 10, 12, 15]
}
}
在真实的外部排序场景中，归并段是磁盘上的文件而不是内存数组，思路完全一致：把堆中取出的元素批量写入输出文件，再从对应文件缓冲读取下一批数据补充进堆。为了减少磁盘 IO，通常会加大每次读写的缓冲区大小，并适当控制归并的路数 k，因为 k 越大堆操作越频繁，k 太小则归并轮数增多，需要根据磁盘性能找到平衡点。
总结一下，从最基础的双指针两路合并，到复用辅助数组的递归归并排序，再到基于小顶堆的多路归并，这套循序渐进的思路覆盖了从小规模内存排序到海量数据外部排序的完整链路。理解了有序数组合并这一个核心操作，归并排序和外部排序的原理也就一目了然了。建议动手把上面的代码跑一遍，再尝试改造为支持降序排列或泛型版本，加深理解。