928 字
2 分钟
归并排序
1. 算法策略
归并排序是建立在归并操作上的一种稳定排序算法，也是分治法的典型应用。
它的核心流程可以概括为三个动作：分 治 合
- 分：将序列一步步分解成小的子序列进行分段排序。
- 治：将分段有序的子序列合并在一起，使得整个序列变得有序。
下图展示了分治策略的整体步骤：
1.1 先拆再并
归并排序的思路可以概括为：
- 不断把数组从中间一分为二。
- 直到每个子数组只剩一个元素。
- 再把两个有序子数组合并成一个更大的有序数组。
例如数组 6 5 3 1 8 7 2 4，拆分过程大致如下：
6 5 3 1 8 7 2 4├── 6 5 3 1│ ├── 6 5│ │ ├── 6│ │ └── 5│ └── 3 1│ ├── 3│ └── 1└── 8 7 2 4 ├── 8 7 │ ├── 8 │ └── 7 └── 2 4 ├── 2 └── 4等到最底层只剩单个元素时，每一段天然就是有序的，接下来只需要逐层合并即可。
分裂点一般写成：
int mid = left + (right - left) / 2;这样写比直接用 (left + right) / 2 更安全，避免区间很大时出现整数溢出。
2. 合并过程
下图以最后一步中合并分段有序的子序列为例：
双指针落位与比较
设立两个指针 left 和 right，分别指向左右两个待合并的已有序子数组 nums[low, mid] 和 nums[mid + 1, high]：
- 在合并左右两个子数组时，若
nums[right] < nums[left]，则将当前较小的nums[right]放入排序结果中。 - 依次类推，直到两个子数组的所有元素都被合并，即可得到最终排好序的数组。
可以拿下面这组数据理解：
- 左子数组：
[2, 4, 6] - 右子数组：
[1, 3, 5]
合并时先比较 2 和 1，取较小的 1；再比较 2 和 3，取 2；接着是 4 和 3，取 3，直到一边元素全部取完，再把另一边剩余元素直接追加进去。
为什么要用临时数组
合并时不能直接在原数组上覆盖，否则后面的元素很容易被提前改掉。
因此通常会先用一个临时数组 tmp 保存合并结果，最后再统一写回原数组。
在 Java 里，更推荐在排序开始前只创建一次辅助数组，然后在递归过程中重复使用它，这样可以减少频繁创建临时对象带来的额外开销。
稳定性
归并排序是稳定排序。
当左右两边出现相同元素时，先取左边的元素，就能保证相同元素的相对顺序不被打乱。
3. Java 实现
下面给出 Java 语言的实现，关键步骤都加了注释。这里采用“只创建一次辅助数组”的写法：
import java.util.Arrays;
public class MergeSort {
public static void mergeSort(int[] arr) { if (arr == null || arr.length <= 1) { return; }
// 只申请一次辅助数组，递归过程中复用 int[] temp = new int[arr.length]; sort(arr, 0, arr.length - 1, temp); }
private static void sort(int[] arr, int left, int right, int[] temp) { // 区间长度为 1 时自然有序，递归结束 if (left >= right) { return; }
// 分：把区间拆成左右两半 int mid = left + (right - left) / 2; sort(arr, left, mid, temp); sort(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; int k = left; while (k <= right) { arr[k++] = temp[t++]; } }
public static void main(String[] args) { int[] arr = {38, 27, 43, 3, 9, 82, 10}; System.out.println("排序前: " + Arrays.toString(arr)); mergeSort(arr); System.out.println("排序后: " + Arrays.toString(arr)); }}NOTE在合并步骤中，如果遇到相等的元素，优先保留左侧子数组中的元素，这也保证了归并排序的稳定性。
TIP如果想优化空间开销，可以把
tmp复用成一个全局辅助数组，避免每次递归都重新创建临时数组。
5. 复杂度分析
- 时间复杂度：。无论最好、最坏还是平均情况，归并排序都要经历“分解 + 合并”两类操作，所以它的时间复杂度都很稳定。
- 空间复杂度：，主要来自辅助数组。递归调用本身还会带来 的栈空间，但通常不作为主导项。
- 稳定性：稳定。合并时若相等元素优先取左边，就能保持相同元素的相对顺序。
分享
如果这篇文章对你有帮助，欢迎分享给更多人！
部分信息可能已经过时
相关文章 智能推荐
1
快速排序
Algorithm 用挖坑填数法讲清快速排序中的 partition 划分过程，以及基准值最终落位的含义。
2
快速幂
Algorithm 通过迭代（二进制角度）与递归（分治法角度）两种方法详细解析快速幂算法，解决数值的整数次幂问题，并将时间复杂度优化至 O(log n)。
3
第二大元素问题
Algorithm 从两种题型出发，介绍一次遍历和分治两种解法，重点讲清分治合并时的候选淘汰思想。
4
堆排序
Algorithm 堆排序利用完全二叉树结构的大根堆或小根堆性质，通过建堆与交替调整实现原地升序或降序排列。
5
最优装载
Algorithm 用最优装载问题理解 LeetCode 1833. 雪糕的最大数量：优先购买价格最低的雪糕，并补充计数排序优化。