归并排序是一种效率稳定的排序算法，时间复杂度始终为O(n log n)，其核心实现依赖于分治法思想，将大问题拆分为小问题逐个解决后再合并结果。分治法的核心逻辑可以拆分为三个步骤，分别是拆分、解决、合并，在归并排序中分别对应数组的拆分、子数组的排序、有序子数组的合并。
归并排序的分治法思想
分治法在归并排序中的体现非常直观，首先将待排序的数组从中间位置拆分为左右两个子数组，然后分别对左右子数组继续执行拆分操作，直到每个子数组只剩下一个元素。单个元素的数组本身已经是有序的，此时就可以开始执行合并操作，将两个有序的子数组合并成一个更大的有序数组，最终得到完整的有序数组。
整个拆分过程是一个递归的过程，递归的终止条件就是子数组的长度为1，此时不需要再继续拆分。拆分阶段的代码逻辑相对简单，只需要计算中间索引，然后递归处理左右区间即可。
合并逻辑的实现细节
合并操作是归并排序的核心，需要将两个已经有序的子数组合并成一个新的有序数组。合并过程通常需要借助一个临时数组来存储合并后的结果，具体步骤如下：
- 定义两个指针分别指向两个子数组的起始位置
- 比较两个指针指向的元素大小，将较小的元素放入临时数组，并移动对应的指针
- 重复上述比较过程，直到其中一个子数组的所有元素都被放入临时数组
- 将另一个子数组剩余的元素直接复制到临时数组中
- 将临时数组中的有序元素拷贝回原数组的对应位置
合并逻辑的正确性依赖于两个子数组本身已经有序，这也是拆分到单个元素后再开始合并的原因，单个元素天然有序，合并后的数组也会保持有序。
完整的C++代码实现
下面是归并排序的完整C++实现代码，包含拆分递归函数和合并函数，以及对外调用的排序入口函数：
#include <iostream>
#include <vector>
using namespace std;
// 合并两个有序子数组的函数
// arr是原数组，left是左子数组起始索引，mid是中间索引，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 m = 0; m < k; m++) {
arr[left + m] = temp[m];
}
}
// 归并排序的递归拆分函数
void mergeSort(vector<int>& arr, int left, int right) {
// 递归终止条件：子数组只有一个元素
if (left >= right) {
return;
}
// 计算中间索引，防止溢出可以写成 left + (right - left) / 2
int mid = (left + right) / 2;
// 递归拆分左子数组
mergeSort(arr, left, mid);
// 递归拆分右子数组
mergeSort(arr, mid + 1, right);
// 合并两个有序子数组
merge(arr, left, mid, right);
}
// 对外调用的排序入口函数
void sortArray(vector<int>& arr) {
if (arr.empty()) {
return;
}
mergeSort(arr, 0, arr.size() - 1);
}
// 测试代码
int main() {
vector<int> testArr = {38, 27, 43, 3, 9, 82, 10};
cout << "排序前的数组：" << endl;
for (int num : testArr) {
cout << num << " ";
}
cout << endl;
sortArray(testArr);
cout << "排序后的数组：" << endl;
for (int num : testArr) {
cout << num << " ";
}
cout << endl;
return 0;
}
算法特性分析
归并排序的时间复杂度在任何情况下都是O(n log n)，因为无论数组初始状态如何，拆分和合并的次数都是固定的。空间复杂度方面，由于合并过程需要临时数组，所以空间复杂度为O(n)，这是归并排序相比快速排序的一个劣势。归并排序是稳定的排序算法，因为在合并过程中，当两个元素相等时，我们会优先取左子数组的元素，不会改变相等元素的原有相对顺序。
实际开发中如果需要稳定的O(n log n)时间复杂度的排序算法，归并排序是非常合适的选择，尤其是在处理链表结构的排序时，归并排序的实现会更加简单，不需要额外的随机访问支持。