分治法归并排序c++

分治法是一种常见的算法设计策略，它将复杂的问题分解成更小的、相似的子问题，然后分别解决，最后再合并结果。归并排序是一种应用了分治思想的经典排序算法。在C++中，归并排序通常通过递归实现。

以下是归并排序的基本步骤：
1. **分割**（Divide）：将数组分为两个相等的子数组，如果数组长度为1，则无需分割，直接返回。
2. **解决**（Conquer）：对每个子数组递归地进行归并排序。
3. **合并**（Combine）：将两个已排序的子数组合并成一个有序数组。这一步是关键，通过比较元素大小，依次添加到新的数组中。

以下是简单的C++代码示例：

#include <vector>
using namespace std;

void merge(vector<int>& arr, int l, int m, int r) {
    int n1 = m - l + 1;
    int n2 = r - m;
    
    vector<int> L(n1), R(n2);
    for (int i = 0; i < n1; i++)
        L[i] = arr[l + i];
    for (int j = 0; j < n2; j++)
        R[j] = arr[m + 1+ j];

    int i = 0, j = 0, k = l;
    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 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);   // 合并两个已排序的部分
    }
}