一、核心思想（分治算法）
归并排序两大阶段：分 + 治
- 分（分割）：不断把当前数组对半拆分成左右两个子数组，直到每个子数组只有1 个元素（单个元素天然有序）。
- 治（合并）：将两个已经有序的子数组，合并成一个有序数组；不断向上合并，最终整个数组有序。
算法特性（面试重点）
- 时间复杂度：稳定 O (nlogn)，最好、最坏、平均都一样，不受原始数组顺序影响
- 空间复杂度：O(n)，需要额外辅助数组
- 稳定排序
- 缺点：需要开辟额外内存，不适合超大数量级内存紧张场景
二、完整代码实现
java
运行
public class MergeSort { public static void main(String[] args) { int[] arr = {8, 4, 5, 7, 1, 3, 6, 2}; System.out.println("排序前："); printArr(arr); // 创建临时数组，避免递归反复创建，优化性能 int[] temp = new int[arr.length]; mergeSort(arr, 0, arr.length - 1, temp); System.out.println("排序后："); printArr(arr); } /** * 递归分割数组 * @param arr 原始数组 * @param left 当前区间左边界 * @param right 当前区间右边界 * @param temp 合并使用的临时数组 */ public static void mergeSort(int[] arr, int left, int right, int[] temp) { // 递归终止条件：区间只有一个元素 if (left >= right) { return; } // 中间分割点 int mid = left + (right - left) / 2; // 递归拆分左区间 [left, mid] mergeSort(arr, left, mid, temp); // 递归拆分右区间 [mid+1, right] mergeSort(arr, mid + 1, right, temp); // 左右两个子区间都有序后，进行合并 merge(arr, left, mid, right, temp); } /** * 合并两个有序区间：[left,mid] 和 [mid+1,right] */ public static void merge(int[] arr, int left, int mid, int right, int[] temp) { int i = left; // 左有序数组起始指针 int j = mid + 1; // 右有序数组起始指针 int t = 0; // temp数组指针 // 依次比较左右两个有序数组，小的放入临时数组 while (i <= mid && j <= right) { if (arr[i] <= arr[j]) { temp[t++] = arr[i++]; } else { temp[t++] = arr[j++]; } } // 左边剩余元素移入temp while (i <= mid) { temp[t++] = arr[i++]; } // 右边剩余元素移入temp while (j <= right) { temp[t++] = arr[j++]; } // 将temp中有序数据拷贝回原数组对应区间 t = 0; while (left <= right) { arr[left++] = temp[t++]; } } // 打印数组 public static void printArr(int[] arr) { for (int num : arr) { System.out.print(num + " "); } System.out.println(); } }三、流程简单推演
数组[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]→[4,8][5]+[7]→[5,7][1]+[3]→[1,3][6]+[2]→[2,6]继续向上合并：
[4,8] + [5,7]→[4,5,7,8][1,3] + [2,6]→[1,2,3,6]最终合并两大块：
[4,5,7,8] + [1,2,3,6]→[1,2,3,4,5,6,7,8]
四、面试对比小结
- 快排：不稳定，原地排序（少量额外空间），平均性能最好；最坏 O (n²)
- 归并排序：稳定，必须 O (n) 辅助空间；复杂度稳定 O (nlogn)
- 堆排序：不稳定，O (1) 额外空间，O (nlogn)
拓展：Java 底层
Arrays.sort()基础类型使用双轴快排； 引用类型使用归并排序（保证稳定）。