在软件开发中，排序是最基础也最频繁的操作之一。当我们需要处理大规模数据时，排序算法的稳定性与最坏情况下的性能保证至关重要。快速排序虽然平均性能优异，但在极端数据下会退化到 O(n²)。而归并排序（Merge Sort）凭借严格的分治策略，能够稳定地保持 O(n log n) 的时间复杂度，并且是少数几种稳定排序算法之一，在数据库查询优化、外部排序等场景中有着不可替代的地位。
本文将用 Java 完整实现归并排序，深入剖析分治思想的”分解-求解-合并”三步曲，并扩展至链表排序与逆序对计数等实战场景。
一、归并排序的核心思想：分而治之
归并排序的策略非常直观：
- 分解（Divide）：将数组从中间一分为二，递归地对左右两半分别排序
- 求解（Conquer）：当子数组长度为 1 时，它天然就是有序的
- 合并（Merge）：将两个已经有序的子数组合并成一个更大的有序数组
这个过程就像整理一副扑克牌：先把牌分成两堆分别排好，再按照大小顺序把两堆牌交错合并成一叠整齐的牌。
1.1 合并操作：双指针的艺术
合并是归并排序的灵魂。假设左右两个子数组已经有序，如何高效地将它们合并？
左半部分: [2, 5, 8] 右半部分: [1, 3, 9]
↑ ↑
left right
比较 2 和 1，取 1 放入结果
比较 2 和 3，取 2 放入结果
比较 5 和 3，取 3 放入结果
...
最终结果: [1, 2, 3, 5, 8, 9]
双指针分别遍历两个有序子数组，每次取较小者放入临时数组，时间复杂度仅为 O(n)。
二、完整Java实现
import java.util.Arrays;
/**
* 归并排序完整实现
* 时间复杂度：最坏/平均/最好均为 O(n log n)
* 空间复杂度：O(n)，需要额外临时数组
* 稳定性：稳定排序
*/
public class MergeSort {
/**
* 对外接口：对数组进行升序归并排序
* @param arr 待排序数组
*/
public static void sort(int[] arr) {
if (arr == null || arr.length <= 1) {
return;
}
// 预先分配临时数组，避免递归过程中反复创建
int[] temp = new int[arr.length];
mergeSort(arr, 0, arr.length - 1, temp);
}
/**
* 递归分治：对 arr[left..right] 区间进行归并排序
* @param arr 原数组
* @param left 区间左边界（包含）
* @param right 区间右边界（包含）
* @param temp 临时数组，用于合并操作
*/
private static void mergeSort(int[] arr, int left, int right, int[] temp) {
// 递归终止条件：区间只有一个元素，天然有序
if (left >= right) {
return;
}
// 取中点，防止整数溢出：left + (right - left) / 2
int mid = left + (right - left) / 2;
// 分解：递归排序左半部分和右半部分
mergeSort(arr, left, mid, temp);
mergeSort(arr, mid + 1, right, temp);
// 合并：将两个有序子数组合并
merge(arr, left, mid, right, temp);
}
/**
* 合并操作：将 arr[left..mid] 和 arr[mid+1..right] 合并为有序数组
* 前提条件：左右两个子数组已经分别有序
*/
private static void merge(int[] arr, int left, int mid, int right, int[] temp) {
// 将待合并区间复制到临时数组
// 注意：只复制当前合并区间，不是整个数组
for (int i = left; i <= right; i++) {
temp[i] = arr[i];
}
int i = left; // 左半部分指针
int j = mid + 1; // 右半部分指针
int k = left; // 结果数组写入位置
// 双指针遍历，取较小者放入原数组
while (i <= mid && j <= right) {
if (temp[i] <= temp[j]) {
arr[k] = temp[i];
i++;
} else {
arr[k] = temp[j];
j++;
}
k++;
}
// 左半部分可能有剩余，直接复制
while (i <= mid) {
arr[k] = temp[i];
i++;
k++;
}
// 右半部分可能有剩余，直接复制
while (j <= right) {
arr[k] = temp[j];
j++;
k++;
}
}
/**
* 可视化辅助方法：打印数组片段
*/
private static void printRange(int[] arr, int left, int right, String label) {
System.out.print(label + " [");
for (int i = left; i <= right; i++) {
System.out.print(arr[i]);
if (i < right) System.out.print(", ");
}
System.out.println("]");
}
// 主程序：演示与测试
public static void main(String[] args) {
// 测试用例1：随机数组
int[] arr1 = {64, 34, 25, 12, 22, 11, 90, 5, 77, 30};
System.out.println("=== 测试1：随机数组 ===");
System.out.println("排序前: " + Arrays.toString(arr1));
MergeSort.sort(arr1);
System.out.println("排序后: " + Arrays.toString(arr1));
System.out.println("验证: " + (isSorted(arr1) ? "通过" : "失败"));
System.out.println();
// 测试用例2：已排序数组（快排最坏情况，归并排序依然 O(n log n)）
int[] arr2 = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
System.out.println("=== 测试2：已排序数组 ===");
System.out.println("排序前: " + Arrays.toString(arr2));
MergeSort.sort(arr2);
System.out.println("排序后: " + Arrays.toString(arr2));
System.out.println();
// 测试用例3：逆序数组
int[] arr3 = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
System.out.println("=== 测试3：逆序数组 ===");
System.out.println("排序前: " + Arrays.toString(arr3));
MergeSort.sort(arr3);
System.out.println("排序后: " + Arrays.toString(arr3));
System.out.println();
// 测试用例4：大量重复元素
int[] arr4 = {5, 5, 5, 1, 1, 3, 3, 3, 3, 2};
System.out.println("=== 测试4：重复元素 ===");
System.out.println("排序前: " + Arrays.toString(arr4));
MergeSort.sort(arr4);
System.out.println("排序后: " + Arrays.toString(arr4));
System.out.println("稳定性验证: 相等元素相对顺序保持不变");
System.out.println();
// 测试用例5：单元素与空数组
int[] arr5 = {42};
MergeSort.sort(arr5);
System.out.println("=== 测试5：单元素 ===");
System.out.println("排序后: " + Arrays.toString(arr5));
int[] arr6 = {};
MergeSort.sort(arr6);
System.out.println("空数组排序: 通过");
}
private static boolean isSorted(int[] arr) {
for (int i = 1; i < arr.length; i++) {
if (arr[i] < arr[i - 1]) {
return false;
}
}
return true;
}
}
三、关键代码解读
3.1 中点计算的防溢出技巧
int mid = left + (right - left) / 2;
当 left 和 right 接近 Integer.MAX_VALUE 时，(left + right) / 2 可能发生整数溢出。使用减法方式可以安全地计算中点。
3.2 临时数组的预分配策略
int[] temp = new int[arr.length];
mergeSort(arr, 0, arr.length - 1, temp);
在整个排序过程中只创建一次临时数组，递归时复用同一块内存，避免了频繁的内存分配与回收开销。
3.3 双指针合并的边界处理
while (i <= mid && j <= right) { ... }
while (i <= mid) { ... } // 处理左半剩余
while (j <= right) { ... } // 处理右半剩余
前两个 while 处理”交错”阶段，后两个 while 处理”收尾”阶段。由于左右子数组已经有序，剩余元素无需比较，直接追加即可。
四、复杂度分析
| 指标 | 归并排序 | 快速排序 | 堆排序 |
|---|---|---|---|
| 平均时间复杂度 | O(n log n) | O(n log n) | O(n log n) |
| 最坏时间复杂度 | O(n log n) | O(n²) | O(n log n) |
| 空间复杂度 | O(n) | O(log n) | O(1) |
| 稳定性 | 稳定 | 不稳定 | 不稳定 |
归并排序的核心优势在于最坏情况保证和稳定性。当数据包含多个关键字、需要保持相等元素的原始相对顺序时（如先按年龄排序、再按姓名排序的多级排序场景），归并排序是理想选择。
五、扩展应用一：链表排序
归并排序非常适合链表结构，因为链表合并无需额外空间，只需调整指针指向即可实现 O(1) 空间复杂度。
/**
* 链表节点的定义
*/
class ListNode {
int val;
ListNode next;
ListNode(int val) { this.val = val; }
}
/**
* 链表归并排序：O(n log n) 时间，O(1) 额外空间
* 经典面试题：LeetCode 148. Sort List
*/
public class LinkedListMergeSort {
public static ListNode sortList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
// 使用快慢指针找到链表中点
ListNode slow = head, fast = head.next;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
// 断开链表为两部分
ListNode rightHead = slow.next;
slow.next = null;
// 递归排序左右两部分
ListNode left = sortList(head);
ListNode right = sortList(rightHead);
// 合并两个有序链表
return merge(left, right);
}
private static ListNode merge(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(0);
ListNode tail = dummy;
while (l1 != null && l2 != null) {
if (l1.val <= l2.val) {
tail.next = l1;
l1 = l1.next;
} else {
tail.next = l2;
l2 = l2.next;
}
tail = tail.next;
}
tail.next = (l1 != null) ? l1 : l2;
return dummy.next;
}
}
快慢指针找中点是链表分治的经典技巧：fast 每次走两步，slow 每次走一步，当 fast 到达末尾时，slow 正好位于中点。
六、扩展应用二：逆序对计数
逆序对是指数组中满足 i < j 且 arr[i] > arr[j] 的数对，常用于衡量数组的”混乱程度”。归并排序的合并过程天然适合统计逆序对数量。
/**
* 利用归并排序统计逆序对数量
* 时间复杂度：O(n log n)
*/
public class InversionCounter {
private long inversionCount = 0;
public long count(int[] arr) {
if (arr == null || arr.length <= 1) {
return 0;
}
int[] temp = new int[arr.length];
mergeSortAndCount(arr, 0, arr.length - 1, temp);
return inversionCount;
}
private void mergeSortAndCount(int[] arr, int left, int right, int[] temp) {
if (left >= right) return;
int mid = left + (right - left) / 2;
mergeSortAndCount(arr, left, mid, temp);
mergeSortAndCount(arr, mid + 1, right, temp);
mergeAndCount(arr, left, mid, right, temp);
}
private void mergeAndCount(int[] arr, int left, int mid, int right, int[] temp) {
for (int i = left; i <= right; i++) {
temp[i] = arr[i];
}
int i = left, j = mid + 1, k = left;
while (i <= mid && j <= right) {
if (temp[i] <= temp[j]) {
arr[k++] = temp[i++];
} else {
// 关键：当右半部分的 temp[j] 更小时
// temp[i..mid] 的所有元素都与 temp[j] 构成逆序对
inversionCount += (mid - i + 1);
arr[k++] = temp[j++];
}
}
while (i <= mid) arr[k++] = temp[i++];
while (j <= right) arr[k++] = temp[j++];
}
public static void main(String[] args) {
int[] arr = {7, 5, 6, 4};
InversionCounter counter = new InversionCounter();
long count = counter.count(arr);
System.out.println("逆序对数量: " + count); // 输出: 5
// 解释: (7,5), (7,6), (7,4), (5,4), (6,4)
}
}
当 temp[j] < temp[i] 时，由于左半部分 temp[i..mid] 已经有序，从 i 到 mid 的所有元素都大于 temp[j]，因此产生 (mid - i + 1) 个逆序对。这是将问题复杂度从 O(n²) 优化到 O(n log n) 的关键。
七、总结
归并排序通过”分而治之”的策略，将复杂的全局排序问题分解为可管理的局部问题，再系统化地合并结果。掌握归并排序不仅意味着掌握一种稳定的排序算法，更意味着理解了分治思想的精髓——这种思维方式在并行计算（如 MapReduce）、外部排序（处理超出内存的数据）以及诸多算法设计场景中都有深远影响。
从代码层面看，归并排序的递归结构和合并逻辑也常被用于解决其他问题：链表重排、区间合并、计算小和、统计翻转对等。熟练掌握归并排序，是进阶算法学习的重要基石。
