归并排序

1. 算法介绍

归并排序是一种高效的 分治法（Divide and Conquer） 排序算法，核心思想：
1️⃣ 分解：将数组递归拆分为最小单位（单个元素）
2️⃣ 合并：将有序子数组合并为更大有序数组
✅ 时间复杂度：最优/平均/最坏均为 O(n log n)
✅ 稳定性：稳定排序（相同元素顺序不变）
✅ 适用场景：大数据量、链表排序、外部排序

2. 分治思想图解

  1. 初始数组： [38, 27, 43, 3, 9, 82, 10]  
  2.             ↓ 分解  
  3. [38, 27, 43]      [3, 9, 82, 10]  
  4.     ↓ 分解             ↓ 分解  
  5. [38] [27, 43]    [3,9] [82,10]  
  6.         ↓ 合并          ↓ 合并  
  7. [27, 38, 43]      [3,9,10,82]  
  8.             ↓ 合并  
  9.      [3,9,10,27,38,43,82]

3. 合并操作详解

核心步骤：合并两个有序数组 

  1. Left数组: [27, 38, 43]   Right数组: [3, 9, 10, 82]  
  2. Step1: 比较左首(27) vs 右首(3) → 取较小值 3  
  3. Step2: 比较 27 vs 9 → 取 9  
  4. Step3: 比较 27 vs 10 → 取 10  
  5. Step4: 直接追加左数组：[27,38,43]  
  6. 结果：[3, 9, 10, 27, 38, 43, 82]

4. C++ 代码实现

  1. #include <vector>
  2. using namespace std;
  4. // 合并两个有序数组
  5. void merge(vector<int>& arr, int left, int mid, int right) {
  6.     vector<int> temp(right - left + 1);
  7.     int i = left, j = mid + 1, k = 0;
  9.     // 合并：取较小值放入temp
  10.     while (i <= mid && j <= right) {
  11.         if (arr[i] <= arr[j]) temp[k++] = arr[i++];
  12.         else temp[k++] = arr[j++];
  13.     }
  15.     // 拷贝剩余元素
  16.     while (i <= mid) temp[k++] = arr[i++];
  17.     while (j <= right) temp[k++] = arr[j++];
  19.     // 拷贝回原数组
  20.     for (int idx = 0; idx < k; idx++) 
  21.         arr[left + idx] = temp[idx];
  22. }
  24. // 归并排序主函数
  25. void mergeSort(vector<int>& arr, int left, int right) {
  26.     if (left >= right) return; // 递归终止条件
  28.     int mid = left + (right - left) / 2;
  29.     mergeSort(arr, left, mid);   // 递归排序左半部
  30.     mergeSort(arr, mid + 1, right); // 递归排序右半部
  31.     merge(arr, left, mid, right);  // 合并有序数组
  32. }
  34. // 调用示例
  35. int main() {
  36.     vector<int> arr = {38, 27, 43, 3, 9, 82, 10};
  37.     mergeSort(arr, 0, arr.size() - 1);
  38.     return 0;
  39. }

5. 关键点分析

🔹 递归深度：共 log₂n 层分解
🔹 合并成本：每层合并需 O(n) 操作
🔹 空间复杂度：O(n)（临时数组开销）
🔹 优化策略：

  • 小数组用插入排序减少递归开销
  • 避免频繁内存分配（全局复用 temp 数组）

6. 与快速排序对比

特性 归并排序 快速排序
最坏时间复杂度 O(n log n) O(n²)
稳定性 ✅ 稳定 ❌ 不稳定
空间复杂度 O(n) O(log n) 栈空间
适用场景 大数据量/外部排序 内存排序/随机数据

7. 可视化演示推荐

🔗 归并排序动画演示
（动态理解分解与合并过程）

总结：归并排序以 时间换空间，凭借稳定且可预测的性能，成为大规模数据排序的基石算法！