归并排序算法详解（C++ 递归实现）

归并排序是一种采用分治策略的排序算法，其主要思想是将待排序的数组不断拆分，直到每个子数组只有一个元素，然后将这些子数组合并成一个有序的数组。合并的过程中，采用稳定的排序算法（如插入排序）对子数组进行排序，最终得到全局有序的数组。

在C++中，归并排序可以通过递归实现。下面是一个基本的归并排序算法实现：

#include <iostream>
#include <vector>
using namespace std;
// 合并两个有序数组
void merge(vector<int>& arr, int l, int m, int r) {
    vector<int> temp(r - l + 1);
    int i = l, j = m + 1, k = 0;
    while (i <= m && j <= r) {
        if (arr[i] <= arr[j]) {
            temp[k++] = arr[i++];
        } else {
            temp[k++] = arr[j++];
        }
    }
    while (i <= m) {
        temp[k++] = arr[i++];
    }
    while (j <= r) {
        temp[k++] = arr[j++];
    }
    for (int p = 0; p < temp.size(); p++) {
        arr[l + p] = temp[p];
    }
}
// 递归实现归并排序
void mergeSort(vector<int>& arr, int l, int r) {
    if (l < r) {
        int m = l + (r - l) / 2; // 计算中间位置
        mergeSort(arr, l, m); // 递归拆分左半部分
        mergeSort(arr, m + 1, r); // 递归拆分右半部分
        merge(arr, l, m, r); // 合并左右两个有序子数组
    }
}

这个实现中，merge函数用于合并两个有序数组，而mergeSort函数则是递归地将数组拆分和合并的过程。在mergeSort函数中，首先计算出中间位置m，然后递归地调用自身对左半部分和右半部分进行排序，最后调用merge函数将两个有序的子数组合并成一个有序的数组。

性能分析：归并排序的时间复杂度为O(nlogn)，其中n为待排序数组的长度。这是因为每次递归拆分都将问题规模减半，合并的过程则需要进行线性扫描。归并排序的空间复杂度为O(n)，因为在合并过程中需要额外的存储空间来存储临时数组。由于归并排序是稳定的排序算法，它能够保持相等元素的相对顺序不变。

在实际应用中，由于归并排序的时间复杂度为O(nlogn)，它通常在处理大规模数据时表现出较好的性能。然而，由于其空间复杂度为O(n)，如果内存资源有限，使用归并排序可能会造成较大的内存开销。因此，在实际应用中需要根据具体需求和资源限制来选择合适的排序算法。