Java 归并排序：稳定排序的"秩序守护者"
分而治之的典范——拆到最小，再有序合并
引言
归并排序（Merge Sort）把数组拆成两半分别排好，再像合并有序链表一样合二为一。
最大优点：稳定 + 稳定 O(n log n)。代价是需要额外 O(n) 空间。
它是少数几个能保证最坏情况也是 O(n log n)的排序算法（不像快排最坏 O(n²)），也是链表排序的最优解（快排对链表不友好）。
这篇文章，我会把归并排序讲透：
- 用 ASCII 图演示"拆分"和"合并"的完整过程
- 推导为什么
mid = left + (right - left) / 2防溢出 - 列出 4 个高频易错点（尤其是边界条件）
- 配套 LeetCode 148（链表归并排序）和 剑指 Offer 51（逆序对）
1. 核心思想：拆到不能再拆，再合并回来
1.1 通俗理解
归并排序的精髓：先递归拆分，再归并合并。
想象你要整理一堆混在一起的扑克牌：
1. 把牌堆从中间分成两半 2. 左边那堆继续分两半 3. 右边那堆继续分两半 4. 直到每堆只剩 1 张牌（天然有序） 5. 两两合并，合并时按顺序选小的 6. 最终合成一个有序牌堆1.2 ASCII 图解演示
以数组[38, 27, 43, 3, 9, 82, 10]为例：
拆分过程（自顶向下）： [38, 27, 43, 3, 9, 82, 10] / \ [38, 27, 43, 3] [9, 82, 10] / \ / \ [38, 27] [43, 3] [9, 82] [10] / \ / \ / \ | [38] [27] [43] [3] [9] [82] [10] 合并过程（自底向上）： [38] [27] [43] [3] [9] [82] [10] \ / \ / \ / | [27, 38] [3, 43] [9, 82] [10] \ / \ / [3, 27, 38, 43] [9, 10, 82] \ / [3, 9, 10, 27, 38, 43, 82]1.3 merge 的细节图解
以合并[27, 38]和[3, 43]为例：
左：[27, 38] 右：[3, 43] temp: [] 步骤 1：左指针 i=0（27），右指针 j=0（3） 27 > 3 → temp = [3]，j++ 步骤 2：i=0（27），j=1（43） 27 < 43 → temp = [3, 27]，i++ 步骤 3：i=1（38），j=1（43） 38 < 43 → temp = [3, 27, 38]，i++ 步骤 4：i=2（越界）→ 把右半部分剩余 [43] 全部搬入 temp = [3, 27, 38, 43] 最后把 temp 拷贝回 arr[left..right]1.4 三个关键观察
- 拆分是 O(log n) 层——每层递归深度增加 1
- 每层合并是 O(n)——n 个元素都要比较一次
- 总复杂度 = O(n) × O(log n) = O(n log n)
2. 完整 Java 实现
importjava.util.Arrays;publicclassMergeSort{/** * 归并排序入口 */publicstaticvoidmergeSort(int[]arr){if(arr==null||arr.length<2){return;}mergeSort(arr,0,arr.length-1);}/** * 递归拆分 */privatestaticvoidmergeSort(int[]arr,intleft,intright){// 递归终止：区间只剩 0 或 1 个元素if(left>=right){return;}// 防溢出写法（不用 (left + right) / 2）intmid=left+(right-left)/2;mergeSort(arr,left,mid);mergeSort(arr,mid+1,right);merge(arr,left,mid,right);}/** * 合并两个有序子数组 arr[left..mid] 和 arr[mid+1..right] */privatestaticvoidmerge(int[]arr,intleft,intmid,intright){// 创建临时数组int[]temp=newint[right-left+1];inti=left,j=mid+1,k=0;// 双指针合并while(i<=mid&&j<
