c++使用分治策略求解二路归并排序算法。

在C++中，二路归并排序是一种经典的分治算法，用于对数组进行排序。它将数组分为两个独立的部分，分别递归地进行排序，然后合并这两个已排序的部分。以下是基本步骤：

1. **划分阶段** (Divide):
- 将待排序数组一分为二，通常可以使用两个指针i和j，初始位置分别为0和数组长度减1。
- 当i < j时，比较arr[i]和arr[j]，较小的那个元素放入临时数组temp，并更新对应的指针（如果arr[i] <= arr[j]，则i++,否则j--）。

2. **递归处理** (Conquer):
- 对左右两个部分递归地应用同样的过程，直到每个部分只有一个元素，此时视为有序。

3. **合并阶段** (Combine):
- 创建一个新的空数组来存放合并后的结果。
- 取左半部分和右半部分的第一个元素进行比较，将较小的元素放入新数组，然后移动指向较小元素的指针（向左半部分或右半部分移动）。这个过程一直持续到任一半部分的元素都添加到结果数组中。

4. **结束条件**:
- 当所有元素都被合并到结果数组后，返回结果数组，即完成排序。

void mergeSort(int arr[], int left, int right) {
    if (left < right) {
        int mid = (left + right) / 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 temp[right - left + 1]; // 存储合并结果
    int i = left, j = mid + 1, k = 0;

    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j]) {
            temp[k++] = arr[i++];
        } else {
            temp[k++] = arr[j++];
        }
    }

    // 把剩余未加到temp的元素复制回原数组
    while (i <= mid) {
        temp[k++] = arr[i++];
    }

    while (j <= right) {
        temp[k++] = arr[j++];
    }

    // 把temp数组的内容复制回原数组
    for (i = left; i <= right; i++) {
        arr[i] = temp[i - left];
    }
}