归并排序核心思想
分治法（Divide and Conquer）
- 分解：将数组从中间分成两半
- 解决：递归地对两半分别排序
- 合并：将两个有序数组合并成一个有序数组
图解示例
假设待排序数组：[8, 4, 5, 7, 1, 3, 6, 2]
第一阶段：分解（递归拆分）
[8,4,5,7,1,3,6,2] ← 原始数组 (0-7) ↓ ┌────────────┴────────────┐ [8,4,5,7] [1,3,6,2] ← mid=3，分成两半 ↓ ↓ ┌────┴────┐ ┌────┴────┐ [8,4] [5,7] [1,3] [6,2] ↓ ↓ ↓ ↓ ┌─┴─┐ ┌─┴─┐ ┌─┴─┐ ┌─┴─┐ [8] [4] [5] [7] [1] [3] [6] [2] ← 递归终止（只剩1个元素） ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ [4,8] [5,7] [1,3] [2,6] ← 开始合并（每层合并） ↓ ↓ ↓ ↓ [4,5,7,8] [1,2,3,6] ← 继续向上合并 ↓ ↓ [1,2,3,4,5,6,7,8] ← 最终有序数组第二阶段：合并过程详解
以合并[4,8]和[5,7]为例：
左数组 [4, 8] 右数组 [5, 7] 临时数组 [] ↑ ↑ i (left) j (mid+1) 步骤1: 4 ≤ 5? 是 → temp[0] = 4, i++, k++ 左 [4, 8] 右 [5, 7] temp [4] ↑ ↑ i j 步骤2: 8 ≤ 5? 否 → temp[1] = 5, j++, k++ 左 [4, 8] 右 [5, 7] temp [4, 5] ↑ ↑ i j 步骤3: 8 ≤ 7? 否 → temp[2] = 7, j++, k++ 左 [4, 8] 右 [5, 7] temp [4, 5, 7] ↑ ↑ i (j超出右边界) 步骤4: 右数组已空，将左数组剩余元素复制 temp[3] = 8 temp = [4, 5, 7, 8] 步骤5: 将temp复制回原数组 arr[left..right] 原数组对应位置变为 [4, 5, 7, 8]代码关键点解析
| 代码段 | 作用 |
|---|---|
int[] temp = new int[arr.length] | 只创建一次临时数组，避免递归中重复分配内存 |
mid = (left + right) / 2 | 计算中点，将数组分成两半 |
sort(arr, left, mid, temp) | 递归排序左半部分 |
sort(arr, mid+1, right, temp) | 递归排序右半部分 |
while (i <= mid && j <= right) | 双指针比较，取较小者放入temp |
while (i <= mid)/while (j <= right) | 处理剩余元素 |
arr[left + i] = temp[i] | 将排序好的temp复制回原数组 |
时间 & 空间复杂度
┌─────────────┬─────────────┐ │ 时间复杂度 │ O(n log n) │ ← 每层O(n)，共log n层 ├─────────────┼─────────────┤ │ 空间复杂度 │ O(n) │ ← 临时数组temp ├─────────────┼─────────────┤ │ 稳定性 │ 稳定 │ ← arr[i] <= arr[j] 保证相等时先取左边 └─────────────┴─────────────┘递归调用栈可视化
sort(0,7) ← 第1层调用 ├─ sort(0,3) ← 第2层 │ ├─ sort(0,1)← 第3层 │ │ ├─ sort(0,0) 返回 │ │ ├─ sort(1,1) 返回 │ │ └─ merge(0,0,1) → [4,8] │ ├─ sort(2,3) │ │ ├─ sort(2,2) 返回 │ │ ├─ sort(3,3) 返回 │ │ └─ merge(2,2,3) → [5,7] │ └─ merge(0,1,3) → [4,5,7,8] └─ sort(4,7) ← 类似右半部分...核心要点：先递归到底（分解到单个元素），再逐层向上合并！
代码实现
publicclassMergeSort{// 归并排序入口publicstaticvoidmergeSort(int[]arr){int[]temp=newint[arr.length];sort(arr,0,arr.length-1,temp);}// 递归分解privatestaticvoidsort(int[]arr,intleft,intright,int[]temp){if(left<right){intmid=(left+right)/2;sort(arr,left,mid,temp);// 左半部分sort(arr,mid+1,right,temp);// 右半部分merge(arr,left,mid,right,temp);// 合并}}// 合并两个有序数组privatestaticvoidmerge(int[]arr,intleft,intmid,intright,int[]temp){inti=left;// 左序列指针intj=mid+1;// 右序列指针intk=0;// 临时数组指针// 比较并放入临时数组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++];// 复制回原数组for(i=0;i<k;i++){arr[left+i]=temp[i];}}}
 - seqlock)