核心思路
归并排序基本思想是将一个数组分成两个子数组，分别对这两个子数组进行排序，然后将排好序的子数组合并成一个最终的有序数组，即分治法：
- 分：将数组递归拆分成左右两半，直到每个子数组只剩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]
