c++中如何实现归并排序_c++分治思想归并排序算法【详解】

归并排序的核心是分治三步：split切分、merge合并、combine写回；merge需用临时数组、半开区间、正确边界控制，且应复用辅助空间而非重复分配。

归并排序的核心逻辑是分治，不是递归本身

归并排序的正确理解起点不是“写个递归函数”，而是明确三步：split（切分到单元素）、merge（合并两个有序段）、combine（把合并结果写回原数组）。递归只是实现 split 的自然手段，但容易让人忽略 merge 的边界控制——这才是实际编码出错最多的地方。

• 切分时用 [left, right) 半开区间比 [left, right] 更少出错，避免 mid = (left + right) / 2 溢出可改用 mid = left + (right - left) / 2
• merge 必须用临时数组暂存结果，不能边合并边写回原数组，否则会覆盖未读取的数据
• 合并循环的终止条件不是“两个子数组都空”，而是“至少一个已耗尽”，剩余部分直接拷贝

标准实现中 merge 函数的四个关键参数

很多初学者把 merge 写成只接受两个独立数组的函数，这在归并排序里反而增加复杂度。实际应传入原数组指针 + 三段下标：arr、left、mid、right（mid 是左半段末尾+1，即右半段起始位置）。

• left 到 mid-1 是左有序段
• mid 到 right-1 是右有序段
• 合并结果要填回 arr[left] 到 arr[right-1]
• 临时数组大小必须是 right - left，而非固定长度或 arr.size()

避免内存重复分配的常见优化

每次递归都 new 临时数组会导致大量堆分配，尤其对大数组性能敏感。更合理的方式是在顶层调用时一次性分配好辅助空间，全程复用。

void mergeSort(vector& arr) {
    if (arr.size() <= 1) return;
    vector temp(arr.size()); // 一次分配
    mergeSortHelper(arr, temp, 0, arr.size());
}
void mergeSortHelper(vector& arr, vector& temp, int left, int right) {
if (right - left <= 1) return;
int mid = left + (right - left) / 2;
mergeSortHelper(arr, temp, left, mid);
mergeSortHelper(arr, temp, mid, right);
merge(arr, temp, left, mid, right);
}

• temp 作为引用传入，避免拷贝
• merge 内部只操作 temp 的对应区间，再批量拷贝回 arr
• 若用原始指针（如 int*），需额外传入 temp 起始地址，逻辑不变

迭代版归并排序为什么更难写对

递归版天然体现分治结构，而迭代版靠自底向上合并：先两两合并长度为 1 的段，再合并长度为 2 的段……容易错在 right 边界越界和最后一段长度不足时的处理。

企奶奶

一款专注于企业信息查询的智能大模型，企奶奶查企业，像聊天一样简单。

下载

立即学习“C++免费学习笔记（深入）”；

• 外层循环步长 len 从 1 开始，每次翻倍：for (int len = 1; len
• 内层循环起点 i 每次加 2 * len，但 right = min(i + 2 * len - 1, n - 1) 必须取最小值
• 右半段可能不存在（i + len >= n），此时跳过合并
• 即使知道原理，手写迭代版仍建议先跑通递归版，再对照改写，否则调试成本极高

归并排序真正卡住人的地方，从来不是“怎么分”，而是“合并时下标算错一格，整段结果就乱序”，尤其是 mid 和 right 的开闭关系、临时数组拷贝的起始偏移。写完务必用 {5, 2, 4, 7, 1} 这类小样例单步验证 merge 调用前后的子数组内容。