分治算法-递归排序，C++

分治算法是一种将复杂问题分解成较小的、相似的子问题，并递归地解决这些子问题，最后合并结果来得到原问题解的策略。在排序算法中，归并排序就是一种经典的分治策略应用实例。

归并排序的核心思想是“分”和“合”。它首先将数组分为两个长度相等的子数组（如果数组长度不是偶数，则会有一个较短的子数组），然后对每个子数组进行排序，接着合并这两个已排序的子数组。这个过程一直递归下去，直到子数组只剩下一个元素，此时视为已排序。合并操作是通过比较两个子数组的首元素，将较小的放入结果数组，然后移动指针继续比较，直至完成。

在C++中，你可以使用递归来实现归并排序。下面是一个简单的示例：

void mergeSort(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 merge(int arr[], int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;

    // 创建临时数组
    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];

    // 合并临时数组回原数组
    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++;
    }
}