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