归并排序采用分治思想，先递归分割数组至单元素，再合并有序子数组，时间复杂度恒为O(n log n)，空间复杂度O(n)，稳定且适合大规模数据。
归并排序是一种典型的分治算法，通过将数组不断分割成两部分，分别排序后再合并，最终得到有序序列。它的时间复杂度稳定在 O(n log n)，适合处理大规模数据排序，且具备稳定性（相等元素的相对位置不变）。
归并排序的基本思想
分治策略：将一个大问题分解为多个小问题解决，再将结果合并。
归并排序分为两个阶段：
- 分解：递归地将数组从中点拆分为左右两部分，直到子数组长度为1。
- 合并：将两个已排序的子数组合并成一个有序数组。
代码实现（C++）
// 归并排序 C++ 实现 #include <iostream> #include <vector> using namespace std;// 合并两个有序区间 [left, mid] 和 [mid+1, right] void merge(vector<int>& arr, int left, int mid, int right) { vector<int> temp(right - left + 1); // 临时数组存储合并结果 int i = left; // 左子数组指针 int j = mid + 1; // 右子数组指针 int k = 0; // 临时数组指针
// 比较并合并
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 (int p = 0; p < k; p++) {
arr[left + p] = temp[p];
}}
立即学习“C++免费学习笔记（深入）”；
// 主排序函数：递归实现 void mergeSort(vector<int>& arr, int left, int right) { if (left < right) { int mid = left + (right - left) / 2; // 防止整数溢出 mergeSort(arr, left, mid); mergeSort(arr, mid + 1, right); merge(arr, left, mid, right); } }
// 使用示例 int main() { vector<int> nums = {38, 27, 43, 3, 9, 82, 10}; cout << "原始数组: "; for (int x : nums) cout << x << " "; cout << endl;
mergeSort(nums, 0, nums.size() - 1); cout << "排序后数组: "; for (int x : nums) cout << x << " "; cout << endl; return 0;
}
算法分析
时间复杂度：无论最好、最坏还是平均情况，都是 O(n log n)。每次划分耗时 O(log n)，每层合并总共需要 O(n) 时间。
组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。
空间复杂度：O(n)，因为需要一个与原数组等长的临时数组用于合并操作。
稳定性：是稳定排序算法。合并过程中，当左右元素相等时优先取左边，保持了原有顺序。
适用场景：
- 对时间稳定性要求高的系统。
- 链表排序（不需要额外数组，可用指针连接）。
- 外部排序（数据量超过内存，需分块读取）。
优化建议
虽然归并排序性能稳定，但仍有优化空间：
- 小数组切换为插入排序：当子数组长度小于10左右时，插入排序更高效。
- 避免频繁创建临时数组：可提前分配一个辅助数组，在整个排序过程中复用。
- 非递归实现（自底向上）：通过控制子数组大小迭代合并，避免递归开销。
基本上就这些。归并排序结构清晰、逻辑严谨，是理解分治思想的经典范例。掌握它的实现和原理，对提升算法思维很有帮助。不复杂但容易忽略细节，比如边界处理和临时数组管理。
