核心思路
归并排序基本思想是将一个数组分成两个子数组，分别对这两个子数组进行排序，然后将排好序的子数组合并成一个最终的有序数组，即分治法：
- 分：将数组递归拆分成左右两半，直到每个子数组只剩1个元素（天然有序）。
- 治：将两个有序子数组合并为一个有序数组，直到合并成完整数组。
优缺点
| 优点 | 缺点 |
|---|---|
| ✅ 稳定排序（相等元素顺序不变） | ❌ 额外空间（需O(n)临时数组） |
| ✅ 时间复杂度稳定O(n logn) | ❌ 递归可能栈溢出（极大数据量时） |
| ✅ 适合大数据量、外排序 | ❌ 对小数据量效率不如插入排序 |
适用范围
- 大数据量
- 稳定性高要求（多次排序顺序必须相同）
- 外排序（处理无法一次性装入内存的数据，如大文件拆散排序）
- 链表排序（归并排序是链表排序的最佳选择之一）
复杂度
时间复杂度：O(n logn)，空间复杂度：O(n)
代码实现（Java）
public class MergeSort {
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);
}
private static void mergeSort(int[] arr, int left, int right, int[] temp) {
//递归终止条件：只剩1个元素
if (left >= right){
return;
}
//分成左右子区间递归排序（逻辑分开，没有物理分开）
int mid = left + (right - left)/2;
mergeSort(arr, left, mid, temp);
mergeSort(arr, mid + 1, right, temp);
//合并左右两部分
merge(arr, left, mid, right, temp);
}
private static void merge(int[] arr, int left, int mid, int right, int[] temp) {
//左半部分起始
int i = left;
//右半部分起始
int j = mid + 1;
//临时数组索引
int t = 0;
//左右两部分按大小顺序合并到临时数组
while (i <= mid && j <= right) {
//强稳定性关键：相等时也取左区间元素
if (arr[i] <= arr[j]) {
temp[t++] = arr[i++];
}else {
temp[t++] = arr[j++];
}
}
//剩余元素拷贝到临时数组
while (i <= mid) temp[t++] = arr[i++];
while (j <= right) temp[t++] = arr[j++];
//将临时数组数据拷贝回原数组
t = 0;
while (left <= right){
arr[left++] = temp[t++];
}
}
}流程示例
1.原始数组： [8,3,5,1,7,4]
2.第一次分解 → [8,3,5] 和 [1,7,4]
3.继续分解左半部分：[8,3,5] → [8,3] 和 [5]，[8,3] → [8] 和 [3]
继续分解右半部分：[1,7,4] → [1,7] 和 [4] [1,7] → [1] 和 [7]
4.合并 [8] 和 [3] → [3,8]
5.合并 [3,8] 和 [5] → [3,5,8]（左半部分完成）
6.合并 [1] 和 [7] → [1,7]
7.合并 [1,7] 和 [4] → [1,4,7]（右半部分完成）
8.合并左右两部分 [3,5,8] 和 [1,4,7] → [1,3,4,5,7,8]