LeetCode 912： 排序数组 （归并排序） —— 题解

👋 欢迎阅读

🔥愿旖旎· 个人主页

📘学习专栏：《算法专栏》《LangChain学习》《贪心算法》

🌄 钱塘江上潮信来，今日方知我是我

✨当前学习内容：《归并排序》

一.题目

912. 排序数组 - 力扣（LeetCode）

🎯 欢迎来到「排序数组」题解之旅！本文将带你从"把两摞已排好的牌合并成一摞"这一直观场景出发，深入理解归并排序（分治）的巧妙运用，并掌握如何递归二分 + 双指针合并来在 O(n log n) 内完成排序。

在开始之前，建议你先：

• 了解题目背景：这是 LeetCode 912 题，给定整数数组nums，要求按升序排序并返回，不能使用内置排序函数，数组长度可达5×10⁴。本质上，排序可以分而治之——把数组拆到只剩单个元素（天然有序），再两两合并成有序序列。

• 明确学习目标：掌握归并排序的递归划分与合并技术，理解辅助数组tmp的偏移回填与收尾 while的作用，并熟练处理递归终止与稳定性（<=）等边界情况。

• 准备好环境：建议在本地 IDE 或 LeetCode 在线编辑器中打开代码，边看边运行，亲手验证示例（如nums = [5,2,3,1]输出[1,2,3,5]）。

本文将从问题转化、递归分治、双指针合并、边界防护到代码实现，层层递进。即使你对归并排序还不熟悉，我们也会从"先拆成一个个，再两两拼回有序"这一直觉出发，让你轻松抓住核心思想——分到最细，合而有序。现在，让我们一起递归拆分、双指针合并，把数组排好序吧！ 🔀🎯

​

二、算法分析

1. 问题分析（前置分析）

• 题目要求：对nums升序排序并返回，禁止调用内置排序，长度可达5×10⁴。
• 关键约束：不能直接用sort；数据量大，O(n²) 算法会超时；要求最坏情况也稳定在 O(n log n)。
• 核心思路：归并排序——递归把数组对半拆分到单元素（天然有序），再在回溯时把相邻两段双指针合并；最坏、平均都是 O(n log n)，且天然稳定。

📌 例子：为什么是归并而不是快排/冒泡

nums = [5,2,4,1]：冒泡需约n²/2次比较，n = 5×10⁴时约1.25×10⁹次，必超时；快速排序平均 O(n log n)，但最坏 O(n²)（如已排序数组取末端为基准）。归并排序无论输入如何都是 O(n log n)，且用<=还能保持稳定——在"禁用内置排序 + 大数据量"的约束下最稳妥。

2. 算法策略（归并排序 · 递归分治 + 双指针合并）

核心步骤：

1. 开辅助数组：成员tmp一次性resize(n)，供所有合并轮次复用。
2. 递归终止：if (left >= right) return;（区间只剩 0/1 个元素，天然有序）。
3. 递归拆分：取中点mid = left + (right - left) / 2，分别排序[left, mid]与[mid+1, right]。
4. 双指针合并：cur1从左段起点、cur2从右段起点，每次取较小者写入tmp（<=保证稳定）。
5. 收尾搬运：某一段先耗尽后，把另一段剩余元素依次搬入tmp。
6. 回填原数组：nums[i] = tmp[i - left]，把本轮合并结果写回。

📊 示例（nums = [5,2,4,1]）：

两次小合并产出[2,5]与[1,4]，最后一次大合并把两段按序交错取出，得到[1,2,4,5]✅。

3. 正确性说明

• 拆分正确：每次取中点把区间一分为二（[left, mid]与[mid+1, right]），两段不重不漏，递归直到单元素终止。
• 合并正确：双指针从两段起点推进，每次取较小者写入tmp，保证合并结果的单调性；<=保证相等时先取左段，维持稳定性。
• 收尾完备：某个指针先越界后，另一段的剩余元素必然都更大（或相等），直接依次搬运即可，不会遗漏。
• 回填正确：tmp本轮从下标 0 写起，回填时用tmp[i - left]精确偏移，nums的[left, right]段被完整覆盖为本轮合并结果。

📌 例子：为什么"收尾 while"不能省略

合并[1,2]与[3,4]：主循环依次取1、2后，左段立即耗尽（cur1 > mid），此时右段的3、4还没写入——若只有主循环，tmp只写入了[1,2]，回填后nums的后两位就是旧数据，排序错误。两个收尾 while 专门搬运"另一段的剩余元素"，缺一不可。

4. 实现细节

• 初始化：tmp作为成员变量，在sortArray中resize(n)一次分配；mergeSort(nums, 0, n-1)，区间为闭区间[left, right]。
• 边界防护：if (left >= right) return;（用>=比==更防御）；mid = left + (right - left) / 2（防溢出的写法）；tmp[i - left]回填时偏移必须减 left。
• 复杂度：时间 O(n log n)（共 log n 层，每层合并总代价 O(n)），空间 O(n)（辅助数组tmp）+O(log n)（递归栈）。
• 关键操作：mid = left + (right - left) / 2;（安全取中点）、if (nums[cur1] <= nums[cur2]) tmp[i++] = nums[cur1++];（双指针取小）、nums[i] = tmp[i - left];（偏移回填）。

📌 例子：tmp 为什么要"一次分配、反复复用"

若把tmp声明成局部数组、每次合并都新建vector<int>(len)：n = 5×10⁴时递归会产生约n-1 次合并，即5 万次堆分配，累计分配/释放的数据量约 O(n log n)，且频繁申请释放会拖慢程序、加剧内存碎片。作为成员变量只resize一次，所有轮次复用同一块空间，分配次数从 O(n) 降到1。

5. 返回值

• 返回nums：原地排序完成后的原数组（mergeSort已把结果回填进去），对应题目"返回排序后的数组"。

三.代码

class Solution { vector<int> tmp; // 辅助数组：所有合并轮次复用（只分配一次） public: vector<int> sortArray(vector<int>& nums) { int n = nums.size(); tmp.resize(n); // 一次性开好，避免每次递归都分配 mergeSort(nums, 0, n - 1); // 对闭区间 [0, n-1] 归并排序 return nums; // 结果已回填到 nums 中 } void mergeSort(vector<int>& nums, int left, int right) { // 1. 递归终止：区间只剩 0 或 1 个元素，天然有序 if (left >= right) { return; } // 2. 取中点（防溢出写法），对半拆分 int mid = left + (right - left) / 2; // 3. 分别排序左右两段：[left, mid] 与 [mid+1, right] mergeSort(nums, left, mid); mergeSort(nums, mid + 1, right); // 4. 双指针合并：从两段起点出发，每次取较小者写入 tmp int cur1 = left; // 左段指针 int cur2 = mid + 1; // 右段指针 int i = 0; // tmp 的写入位置（从 0 开始） while (cur1 <= mid && cur2 <= right) { if (nums[cur1] <= nums[cur2]) // 用 <= 保证稳定性 { tmp[i++] = nums[cur1++]; } else { tmp[i++] = nums[cur2++]; } } // 5. 收尾：把尚未耗尽的另一段剩余元素直接搬入 tmp while (cur1 <= mid) { tmp[i++] = nums[cur1++]; } while (cur2 <= right) { tmp[i++] = nums[cur2++]; } // 6. 回填：tmp 从 0 写起，故 nums[i] 对应 tmp[i - left] for (int k = left; k <= right; k++) { nums[k] = tmp[k - left]; } } };

四、易错点分析

难点1：回填时的偏移tmp[i - left]

for (int i = left; i <= right; i++) { nums[i] = tmp[i - left]; }

tmp每轮合并都从下标 0 开始写（i初始为 0），而nums的目标区间是[left, right]，两者起点不同，因此回填必须减去left偏移。若写成nums[i] = tmp[i]，当left > 0时会读到tmp中不属于本段的数据（本轮只写了tmp[0 .. right-left]），导致元素错乱；同时i可能超出本轮写入范围，读到上一轮的旧值。"tmp 从 0 写、回填减 left"是一套配套约定，也可改成"从 left 写、回填直接对应"，但两者不能混用。

难点2：两个收尾while缺一不可

while (cur1 <= mid) tmp[i++] = nums[cur1++]; while (cur2 <= right) tmp[i++] = nums[cur2++];

主循环在任一段耗尽时停止，此时另一段可能还有剩余元素未被写入tmp。合并[1,2]与[3,4]时，主循环取完1、2就退出，3、4必须靠第二个收尾while搬入；省略后tmp后半段是旧数据，回填即出错。两个while分别对应"左段剩余"与"右段剩余"，一个都不能少。

难点3：mid取整与区间划分必须配套

int mid = left + (right - left) / 2; mergeSort(nums, left, mid); // 左段 [left, mid] mergeSort(nums, mid + 1, right); // 右段 [mid+1, right]

mid下取整，故左段是[left, mid]、右段是[mid+1, right]，两段不重不漏。若划分写成[left, mid-1]与[mid, right]，当left == mid（区间长 2）时左段为空、右段仍是原区间，递归永远不缩小 → 无限递归（栈溢出）。另外left + (right - left) / 2避免left + right溢出，是安全取中点的标准写法。

难点4：<=与<决定排序是否稳定

if (nums[cur1] <= nums[cur2]) tmp[i++] = nums[cur1++];

相等时用<=会优先取左段元素，而左段元素在原数组中本就位于右段之前，因此相等元素的相对顺序得以保持——这就是稳定性。若写成<，相等时会先取右段，相对顺序被颠倒，变为不稳定排序。本题只要求升序，稳定性不影响正确性，但归并排序的稳定性是它的重要优势（多关键字排序时必需），写<=是良好习惯。

难点5：递归终止条件left >= right不能漏

if (left >= right) { return; }

递归的"分到最细"终点是区间只剩 1 个元素（此时天然有序，无需合并）。若漏掉这个终止条件，mergeSort会无限自我调用（空区间不收敛），直接栈溢出崩溃。用>=而非==是防御性写法：即使区间意外变空（如错误划分），也能正确返回而不越界。

五、流程图

🎯 闭幕

🎉 恭喜你完成了「排序数组」问题的学习！

为了巩固知识并进一步拓展，建议你：

🚀 动手实践在 LeetCode 上提交代码，尝试不同的测试用例。

💡 深入思考

• 本题采用归并排序，把数组拆到单元素再合并。请问**"单元素天然有序"这一性质在算法中扮演什么角色？它是递归的什么？
• tmp每轮合并从下标 0 开始写，回填用tmp[i - left]。请问为什么要减left？不减会发生什么？
• 两个收尾while缺一不可。请问在什么情况下会触发收尾？省略后为什么只丢"后半段"而不是全部？
• 代码用nums[cur1] <= nums[cur2]。请问**<=与<对排序结果有何影响**？本题需要稳定吗？

如果你觉得本文对你有所帮助，欢迎：

👍 点赞 / 收藏 👤 关注作者，获取更多题解 💬 留言交流你的疑问或优化思路

📌 深入思考答案

• "单元素天然有序"是递归的终止条件——它把"排序整个数组"分解为"排序单元素"这一不需要任何操作的最小单位，再靠合并逐层回溯，这是分治能够收敛的根本。
• tmp本轮从下标 0 写起，而nums的目标区间起点是left，两者起点错开left个位置；不减left会读到tmp中不属于本轮的数据（或上一轮旧值），回填错乱。
• 当某一子段先耗尽时触发收尾（另一段还有剩余）。省略后，主循环只把"能比较的部分"写入tmp，剩余元素没写，回填时只覆盖了部分位置，后半段仍是旧数据——错误表现为部分有序而非全乱。
• <=在相等时先取左段，保持相等元素的相对顺序（稳定）；<会先取右段，稳定性被破坏。本题只要求升序，不需要稳定，但写<=是归并排序的标准做法，为多关键字排序等扩展留余地。

祝你在算法之路上越走越稳，早日攻克每一道难题！下次见 🚀✨