归并排序是一种基于分治策略的经典排序算法，由约翰・冯・诺依曼在 1945 年提出。它以稳定的 O (nlogn) 时间复杂度和良好的可并行性，在大规模数据排序场景中占据重要地位。与快速排序的 “先分区后排序” 不同，归并排序采用 “先排序后合并” 的思路，其稳定性（相等元素相对顺序不变）使其在数据库排序等对稳定性有要求的场景中备受青睐。

归并排序算法核心思路

归并排序的核心思想是分治（Divide and Conquer），即将一个大问题分解为若干个小问题，分别解决后再将结果合并。具体可分为三个步骤：分解（Divide）、治理（Conquer）、合并（Merge）。

关键步骤解析

（1）分解（Divide）

将待排序数组不断二分，直到每个子数组只包含一个元素（此时子数组天然有序）。例如，对数组[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]、[5]、[7]、[1]、[3]、[6]、[2]

（2）治理（Conquer）

递归处理每个子数组，由于当子数组长度为 1 时已天然有序，因此这一步主要是递归的终止条件。

（3）合并（Merge）

将两个有序子数组合并为一个更大的有序数组，这是归并排序的核心步骤。合并过程需借助一个辅助数组，具体步骤如下：

初始化两个指针i和j，分别指向两个子数组的起始位置。

初始化辅助数组指针k，指向辅助数组起始位置。

比较i和j指向的元素，将较小的元素放入辅助数组，并移动对应指针。

重复步骤 3，直到其中一个子数组遍历完毕。

将剩余子数组的元素依次放入辅助数组。

将辅助数组的元素复制回原数组的对应位置。

归并排序的整体流程

归并排序的整体流程是 “分解 - 合并” 的递归过程，可用以下流程图表示：

归并排序的 Java 实现（基础版）

public class MergeSortBasic {// 对外暴露的排序方法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) {if (left < right) {int mid = left + (right - left) / 2; // 避免溢出，等价于(left + right) / 2mergeSort(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 k = left; // 辅助数组起始索引// 比较并合并两个子数组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 (k = left; k <= right; k++) {arr[k] = temp[k];}}// 测试public static void main(String[] args) {int[] arr = {8, 4, 5, 7, 1, 3, 6, 2};sort(arr);for (int num : arr) {System.out.print(num + " "); // 输出：1 2 3 4 5 6 7 8}}}

LeetCode 例题实战

例题 1：912. 排序数组（中等）

题目描述：给你一个整数数组 nums，请你将该数组升序排列。

示例：

输入：nums = [5,2,3,1]

输出：[1,2,3,5]

解题思路：直接使用归并排序对数组进行排序。与快速排序相比，归并排序的时间复杂度稳定为 O (nlogn)，适合处理包含大量重复元素或近乎有序的数组。

Java 代码实现：


class Solution {public int[] sortArray(int[] nums) {if (nums == null || nums.length <= 1) {return nums;}int[] temp = new int[nums.length];mergeSort(nums, 0, nums.length - 1, temp);return nums;}private void mergeSort(int[] arr, int left, int right, int[] temp) {if (left < right) {int mid = left + (right - left) / 2;mergeSort(arr, left, mid, temp);mergeSort(arr, mid + 1, right, temp);merge(arr, left, mid, right, temp);}}private void merge(int[] arr, int left, int mid, int right, int[] temp) {int i = left;int j = mid + 1;int k = left;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 (k = left; k <= right; k++) {arr[k] = temp[k];}}}

复杂度分析：

时间复杂度：O (nlogn)，无论数组初始状态如何，分解和合并的总操作次数均为 O (nlogn)。

空间复杂度：O (n)，来自辅助数组temp。

例题 2：315. 计算右侧小于当前元素的个数（困难）

题目描述：给你一个整数数组 nums ，按要求返回一个新数组 counts 。数组 counts 有该性质：counts[i] 的值是 nums[i] 右侧小于 nums[i] 的元素的数量。

示例：

输入：nums = [5,2,6,1]
输出：[2,1,1,0]
解释：
5 的右侧有 2 个更小的元素 (2 和 1)
2 的右侧有 1 个更小的元素 (1)
6 的右侧有 1 个更小的元素 (1)
1 的右侧没有更小的元素

解题思路：本题可借助归并排序的合并过程统计逆序对。在合并两个有序子数组时，当右子数组元素nums[j]小于左子数组元素nums[i]时，右子数组中j到mid+1的所有元素均小于nums[i]，因此counts[i]需加上right - j + 1（剩余元素个数）。为避免原数组索引被排序打乱，需额外记录元素原始索引。

Java 代码实现：

class Solution {private int[] counts;public List<Integer> countSmaller(int[] nums) {int n = nums.length;counts = new int[n];if (n == 0) {return new ArrayList<>();}// 构建数组，存储值和原始索引int[][] arr = new int[n][2];for (int i = 0; i < n; i++) {arr[i][0] = nums[i];arr[i][1] = i;}int[][] temp = new int[n][2]; // 辅助数组mergeSort(arr, 0, n - 1, temp);// 转换为List返回List<Integer> result = new ArrayList<>();for (int count : counts) {result.add(count);}return result;}private void mergeSort(int[][] arr, int left, int right, int[][] temp) {if (left < right) {int mid = left + (right - left) / 2;mergeSort(arr, left, mid, temp);mergeSort(arr, mid + 1, right, temp);merge(arr, left, mid, right, temp);}}private void merge(int[][] arr, int left, int mid, int right, int[][] temp) {int i = left;int j = mid + 1;int k = left;while (i <= mid && j <= right) {if (arr[i][0] <= arr[j][0]) {// 右子数组中j到right的元素均小于arr[i][0]counts[arr[i][1]] += right - j + 1;temp[k++] = arr[i++];} else {temp[k++] = arr[j++];}}// 左子数组剩余元素，右侧已无元素，无需计数while (i <= mid) {temp[k++] = arr[i++];}// 右子数组剩余元素，左侧已无元素，无需计数while (j <= right) {temp[k++] = arr[j++];}// 复制回原数组for (k = left; k <= right; k++) {arr[k] = temp[k];}}}

复杂度分析：

时间复杂度：O (nlogn)，归并排序的时间复杂度为 O (nlogn)，合并过程中计数操作仅为 O (1)。

空间复杂度：O (n)，来自辅助数组和存储索引的数组。

考研 408 例题解析

例题 1：基本概念与时间复杂度分析（选择题）

题目：下列关于归并排序的叙述中，正确的是（）。
A. 归并排序的时间复杂度为 O (nlogn)，空间复杂度为 O (1)
B. 归并排序是不稳定的排序算法
C. 归并排序在最坏情况下的时间复杂度优于快速排序
D. 归并排序适合对链表进行排序
答案：C、D
解析：
A 错误：归并排序空间复杂度为 O (n)（辅助数组），链表排序可优化至 O (1)，但数组排序仍为 O (n)。
B 错误：归并排序是稳定排序（合并时相等元素按原顺序放置）。
C 正确：归并排序最坏时间复杂度为 O (nlogn)，而快速排序最坏为 O (n²)。
D 正确：链表归并排序无需辅助数组，通过指针操作合并，空间复杂度 O (logn)（递归栈），效率高。

例题 2：算法设计题（408 高频考点）

题目：已知单链表的头指针为head，设计一个算法对该链表进行归并排序，要求时间复杂度为 O (nlogn)，空间复杂度为 O (logn)。

解题思路：链表归并排序与数组归并排序思路一致，但需注意：

分解：通过快慢指针找到链表中点，断开链表为左右两部分。

合并：通过指针操作合并两个有序链表，无需辅助数组。

Java 代码实现：

class ListNode {int val;ListNode next;ListNode(int x) {val = x;next = null;}}public class MergeSortList {public ListNode sortList(ListNode head) {// 基线条件：空链表或单节点链表无需排序if (head == null || head.next == null) {return head;}// 找到链表中点并断开ListNode mid = findMid(head);ListNode rightHead = mid.next;mid.next = null; // 断开// 递归排序左右链表ListNode left = sortList(head);ListNode right = sortList(rightHead);// 合并有序链表return merge(left, right);}// 快慢指针找中点（偶数节点取左中点）private ListNode findMid(ListNode head) {if (head == null) {return null;}ListNode slow = head;ListNode fast = head.next; // 确保偶数时取左中点while (fast != null && fast.next != null) {slow = slow.next;fast = fast.next.next;}return slow;}// 合并两个有序链表private ListNode merge(ListNode l1, ListNode l2) {ListNode dummy = new ListNode(0);ListNode curr = dummy;while (l1 != null < / doubaocanvas >
｝

希望本文能够帮助读者更深入地理解归并排序，并在实际项目中发挥其优势。谢谢阅读！

希望这份博客能够帮助到你。如果有其他需要修改或添加的地方，请随时告诉我。