用cpp设计分治法实现二路归并排序。利用递归思想，实现自上向下的二路归 并排序。

在C++中，我们可以使用分治策略来实现二路归并排序，这是一种稳定的排序算法。以下是基本步骤：

1. **分解** (Divide): 首先将待排序数组分成两半。这是通过计算中间索引来完成的。

int middle = array.size() / 2;
std::vector<int> left_half(array.begin(), array.begin() + middle);
std::vector<int> right_half(array.begin() + middle, array.end());

2. **解决** (Conquer): 对左右两个子数组分别递归地应用相同的排序过程，直到每个子数组只有一个元素，此时视为已排序。

3. **合并** (Combine): 当左右子数组排序完毕后，将它们合并成一个有序数组。可以创建一个新的大数组，并从左、右两个子数组的头部开始比较，较小的元素添加到结果数组，重复这个过程直到一方数组遍历完。

void merge(std::vector<int>& arr, int start, int mid, int end) {
    std::vector<int> temp(end - start + 1);
    int i = start, j = mid + 1, k = 0;

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

    // 将剩余部分复制到temp数组
    while (i <= mid) {
        temp[k++] = arr[i++];
    }

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

    // 把排序好的temp数组复制回原数组
    for (i = start; i <= end; ++i) {
        arr[i] = temp[i - start];
    }
}

// 主函数
void mergeSort(std::vector<int>& arr, int start, int end) {
    if (start < end) {
        int mid = start + (end - start) / 2;
        mergeSort(arr, start, mid); // 分治左边
        mergeSort(arr, mid + 1, end); // 分治右边
        merge(arr, start, mid, end); // 合并结果
    }
}