归并排序基于分治思想，将数组递归二分至单元素后合并为有序数组，C++实现包含分割与合并步骤，时间复杂度恒为O(n log n)，空间复杂度O(n)，稳定且适合大数据量排序。
归并排序是一种高效的稳定排序算法，基于分治思想。它将数组不断二分，直到每个子数组只有一个元素，再将这些子数组两两合并，合并过程中保持有序，最终得到完全有序的数组。C++中实现归并排序，关键在于递归分割和有序合并两个步骤。
归并排序的基本原理
归并排序的核心是“分而治之”：
- 把一个数组从中间分成左右两部分
- 对左右两部分分别递归调用归并排序
- 将排好序的两部分合并成一个有序数组
这个过程持续进行，直到整个数组有序。时间复杂度始终为O(n log n)，不受输入数据影响，空间复杂度为O(n)，需要额外数组存储临时结果。
C++中的归并排序实现
下面是一个完整的C++归并排序实现：
立即学习“C++免费学习笔记（深入）”；
#include <iostream>
#include <vector>
using namespace std;
<p>// 合并两个有序子数组
void merge(vector<int>& arr, int left, int mid, int right) {
int n1 = mid - left + 1;
int n2 = right - mid;</p><pre class='brush:php;toolbar:false;'>// 创建临时数组
vector<int> L(n1), R(n2);
// 复制数据到临时数组
for (int i = 0; i < n1; i++)
L[i] = arr[left + i];
for (int j = 0; j < n2; j++)
R[j] = arr[mid + 1 + j];
// 合并临时数组回到arr[left..right]
int i = 0, j = 0, k = left;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
}
k++;
}
// 复制剩余元素
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}}
// 归并排序主函数 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); } }
// 打印数组 void printArray(const vector<int>& arr) { for (int num : arr) cout << num << " "; cout << endl; }
使用示例与测试
编写main函数来验证归并排序的效果：
int main() {
vector<int> arr = {38, 27, 43, 3, 9, 82, 10};
cout << "原始数组: ";
printArray(arr);
<pre class='brush:php;toolbar:false;'>mergeSort(arr, 0, arr.size() - 1);
cout << "排序后数组: ";
printArray(arr);
return 0;}
输出结果为：
原始数组: 38 27 43 3 9 82 10排序后数组: 3 9 10 27 38 43 82
归并排序的特点与适用场景
归并排序适合对稳定性有要求、数据量较大且分布不均的情况。它的优势包括：
- 时间复杂度稳定，最坏、最好、平均都是O(n log n)
- 排序过程稳定，相等元素相对位置不变
- 适用于链表排序，不需要随机访问
缺点是需要O(n)额外空间，在小规模数据上不如插入排序高效。实际开发中，可以结合插入排序优化：当子数组长度小于某个阈值（如10）时改用插入排序。
基本上就这些。归并排序逻辑清晰，性能可靠，是理解分治算法的经典案例。
