归并排序算法c++模板

### C++ 实现的归并排序算法模板

归并排序是一种基于分治策略的经典排序算法。该算法通过递归方式将数组分割成较小子序列直到每个子序列仅有一个元素，随后逐步合并这些有序子序列形成最终完全有序的结果。

以下是使用 C++ 编写的通用归并排序函数：

#include <vector>
using namespace std;

template<typename T>
void merge(vector<T>& arr, int left, int mid, int right) {
    vector<T> temp;
    int i = left;     // 左半部分起始索引
    int j = mid + 1;  // 右半部分起始索引
    
    while (i <= mid && j <= right){
        if (arr[i] <= arr[j]){
            temp.push_back(arr[i]);
            ++i;
        }
        else{
            temp.push_back(arr[j]);
            ++j;
        }
    }

    // 将剩余未处理的数据加入临时向量
    while(i <= mid){
        temp.push_back(arr[i]);
        ++i;
    }
    
    while(j <= right){
        temp.push_back(arr[j]);
        ++j;
    }

    // 把排好序的部分复制回原数组
    for(int k=left;k<=right;++k){
        arr[k]=temp[k-left];
    }
}

template<typename T>
void mergeSort(vector<T>& arr, int left, int right) {
    if(left >= right){return;} // 单个元素无需排序
    int mid=(left+right)/2;
    mergeSort(arr,left,mid);      // 对左半边进行递归调用
    mergeSort(arr,mid+1,right);   // 对右半边进行递归调用
    merge(arr,left,mid,right);    // 合并两个已排序区间
}

此代码实现了标准的自顶向下归并排序逻辑[^3]。`merge()` 函数负责实际的合并操作；而 `mergeSort()` 则控制整个过程中的划分工作以及何时停止递归。

为了提高性能，在某些情况下可以考虑优化上述基础版本，比如当待排序片段较小时切换到插入排序来减少开销，或是采用更高效的内存管理方案以降低额外空间复杂度。