在排序算法的家族中，归并排序是分治思想的“教科书级典范”，也是大厂技术面试的高频考点——它不仅能稳定实现O(nlogn)的时间复杂度，更适合处理链表排序、大数据外部排序等特殊场景。**归并排序算法的原理与实现**是理解分治思想、稳定排序特性、O(nlogn)时间复杂度的核心载体：掌握它，能帮你快速搭建起复杂算法的思维框架，为后续学习快速排序、堆排序等高级算法打下基础。作为鳄鱼java拥有10年经验的内容编辑，我们接触过上千名算法学员，80%的学员在吃透归并排序后，分治类问题的通过率从30%提升到90%，足见其作为算法入门基石的核心价值。
一、归并排序的核心：分治思想到底是什么？
归并排序的核心是分治思想：将一个复杂问题拆解为多个相同或相似的子问题，逐个解决子问题后，将结果合并得到原问题的解。鳄鱼java算法课导师会用生活化的例子类比：把一本厚书分成多个薄章节，每个章节又分成多个小节，先理解每个小节的内容，再合并小节理解章节，最后合并章节理解整本书——归并排序的逻辑与此完全一致。
与冒泡排序、插入排序等“原地交换”的排序算法不同，归并排序的核心优势在于： 1. 稳定排序：相等元素的相对顺序在排序后保持不变，这对于有排序优先级的场景（比如电商按价格排序时保留相同价格商品的上架顺序）至关重要； 2. 时间复杂度稳定：无论输入数据是否有序，时间复杂度始终为O(nlogn)，避免了快速排序在最坏情况下的O(n²)超时问题； 3. 适合链式结构：无需随机访问即可实现，是链表排序的最优解（比如LeetCode21合并两个有序链表、LeetCode148排序链表）。
二、归并排序算法的原理与实现：分而治之，合而有序
**归并排序算法的原理与实现**可以拆分为两个核心步骤：“分（Divide）”和“合（Merge）”，两者循环往复直到完成排序：
1. 分（Divide）：递归拆分，直到子数组长度为1 将待排序数组从中间位置（mid = (left + right)/2）拆分为左右两个子数组，然后递归拆分左子数组和右子数组，直到每个子数组的长度为1（单个元素可视为有序数组）。例如数组[8,4,5,7,1,3,6,2]，会被拆分为[8,4,5,7]和[1,3,6,2]，继续拆分为[8,4]、[5,7]、[1,3]、[6,2]，直到拆分为[8]、[4]、[5]、[7]、[1]、[3]、[6]、[2]。
2. 合（Merge）：合并两个有序子数组，生成新的有序数组 从最底层的单个元素开始，将两个相邻的有序子数组合并为一个新的有序数组，重复这个过程直到合并为完整的有序数组。例如先合并[8]和[4]得到[4,8]，合并[5]和[7]得到[5,7]，再合并[4,8]和[5,7]得到[4,5,7,8]；同理合并右边的子数组得到[1,2,3,6]，最后合并两个大的有序数组得到[1,2,3,4,5,6,7,8]。
鳄鱼java学员数据显示，80%的新手在“合并”阶段容易出错，核心原因是未正确处理两个子数组的边界，比如当一个子数组遍历完毕后，未将另一个子数组的剩余元素直接追加到结果中。
三、归并排序的Java实现：递归与迭代两种方式
归并排序的实现分为递归和迭代两种方式，鳄鱼java算法课会同时讲解两种实现，帮助学员理解分治的不同落地形式：
1. 递归实现：逻辑直观，适合理解分治思想 递归实现的核心是“先拆分，后合并”，通过递归函数完成拆分，再通过合并函数完成有序数组的合并：
public class MergeSort {
// 归并排序入口
public void mergeSort(int[] arr) {
if (arr == null || arr.length < 2) return;
// 临时数组，避免重复创建，优化空间开销
int[] temp = new int[arr.length];
sort(arr, 0, arr.length - 1, temp);
}
// 递归拆分函数
private void sort(int[] arr, int left, int right, int[] temp) {
if (left >= right) return; // 递归终止条件：子数组长度为1
int mid = left + (right - left) / 2; // 避免(left+right)溢出
// 拆分左子数组
sort(arr, left, mid, temp);
// 拆分右子数组
sort(arr, mid + 1, right, temp);
// 合并左右有序子数组
merge(arr, left, mid, right, temp);
}
// 合并两个有序子数组
private void merge(int[] arr, int left, int mid, int right, int[] temp) {
int i = left; // 左子数组起始索引
int j = mid + 1; // 右子数组起始索引
int k = left; // 临时数组起始索引
// 比较左右子数组元素，按序放入临时数组
while (i <= mid && j <= right) {
// 小于等于保证稳定性
if (arr[i] <= arr[j]) {
temp[k++] = arr[i++];
} else {
temp[k++] = arr[j++];
}
}
// 左子数组剩余元素追加到临时数组
while (i <= mid) {
temp[k++] = arr[i++];
}
// 右子数组剩余元素追加到临时数组
while (j <= right) {
temp[k++] = arr[j++];
}
// 将临时数组的有序元素复制回原数组
System.arraycopy(temp, left, arr, left, right - left + 1);
}
}
2. 迭代实现：避免栈溢出，适合大数据排序 递归实现虽然直观，但当数组长度超过1000时，会出现栈溢出问题，迭代实现通过“自底向上”的合并方式，避免了递归栈的开销：
public class MergeSortIterative {
public void mergeSort(int[] arr) {
if (arr == null || arr.length < 2) return;
int n = arr.length;
int[] temp = new int[n];
// 步长从1开始，每次翻倍，相当于合并的子数组长度
for (int step = 1; step < n; step *= 2) {
// 按步长遍历数组，合并相邻的两个子数组
for (int left = 0; left < n - step; left += 2 * step) {
int mid = left + step - 1;
int right = Math.min(left + 2 * step - 1, n - 1);
merge(arr, left, mid, right, temp);
}
}
}
// 合并函数与递归实现一致
private void merge(int[] arr, int left, int mid, int right, int[] temp) {
int i = left, j = mid + 1, k = left;
while (i <= mid && j <= right) {
temp[k++] = arr[i] <= arr[j] ? arr[i++] : arr[j++];
}
while (i <= mid) temp[k++] = arr[i++];
while (j <= right) temp[k++] = arr[j++];
System.arraycopy(temp, left, arr, left, right - left + 1);
}
}
四、时间与空间复杂度分析：为什么归并是稳定排序？
鳄鱼java算法课导师会用数学推导+实战数据，帮学员彻底理解归并排序的复杂度：
1. 时间复杂度
版权声明
本文仅代表作者观点，不代表百度立场。
本文系作者授权百度百家发表，未经许可，不得转载。
