c＋＋分治法解决合并排序问题 将待排序元素集合分成大小大致相同的2个子集合,分别对2个子集合进行排序，最终将排好序的子集合合并成为一个有序集合。

在C++中，合并排序（Merge Sort）是一种经典的分治算法，用于对整数数组进行排序。以下是合并排序的基本步骤：

1. **分割（Divide）**：首先，将原始数组递归地分为两个相等或接近相等的部分，直到每个部分只包含一个元素。这个过程称为“划分”。

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);
    }
}

2. **合并（Combine）**：然后，将这两个已排序的部分合并为一个有序数组。这是通过创建一个新的临时数组，并按照升序顺序将两个部分逐个元素添加到临时数组中完成的。在C++中，可以使用两个指针来遍历两个部分，将较小的元素放入临时数组，直到其中一个部分遍历完。

void merge(int arr[], int temp[], int left, int mid, int right) {
    int i = left; // 指向左半部分
    int j = mid + 1; // 指向右半部分
    int k = left; // 指向临时数组

    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 (i = left; i <= right; i++) {
        arr[i] = temp[i];
    }
}

3. **递归结束与合并**：最后，在整个数组只剩一个元素或为空的情况下，递归结束。然后调用`merge()`函数合并两个子数组。

void mergeSort(int arr[], int size) {
    if (size > 1) {
        int mid = size / 2;
        int* temp = new int[size]; // 或者动态分配内存
        mergeSort(arr, temp, 0, mid - 1);
        mergeSort(arr, temp, mid, size - 1);
        delete[] temp; // 清理临时数组
        merge(arr, temp, 0, mid - 1, size - 1);
    }
}