设计分治法实现二路归并排序。 利用递归思想，实现自上向下的二路归并排序。给出完整代码

下面是 C++ 实现的自上向下的二路归并排序的代码，采用分治法思想：

#include <iostream>
#include <vector>

using namespace std;

// 合并两个有序数组
void merge(vector<int>& nums, int left, int mid, int right) {
    vector<int> temp(right - left + 1);  // 临时数组
    int i = left;  // 左序列指针
    int j = mid + 1;  // 右序列指针
    int k = 0;  // 临时数组指针

    // 将左右两个有序序列合并
    while (i <= mid && j <= right) {
        if (nums[i] <= nums[j])
            temp[k++] = nums[i++];
        else
            temp[k++] = nums[j++];
    }

    // 将左边剩余元素填充进temp中
    while (i <= mid)
        temp[k++] = nums[i++];

    // 将右边剩余元素填充进temp中
    while (j <= right)
        temp[k++] = nums[j++];

    // 将temp中的元素全部拷贝到原数组中
    for (int p = 0; p < k; p++)
        nums[left + p] = temp[p];
}

// 归并排序递归函数
void mergeSort(vector<int>& nums, int left, int right) {
    if (left >= right) return;  // 递归结束条件

    int mid = left + (right - left) / 2;  // 计算中间位置
    mergeSort(nums, left, mid);  // 对左子序列进行归并排序
    mergeSort(nums, mid + 1, right);  // 对右子序列进行归并排序
    merge(nums, left, mid, right);  // 合并左右两个有序序列
}

// 测试
int main() {
    vector<int> nums = {4, 7, 2, 8, 1, 9, 6, 3, 5};
    mergeSort(nums, 0, nums.size() - 1);
    for (int num : nums) {
        cout << num << " ";
    }
    return 0;
}

输出结果为：1 2 3 4 5 6 7 8 9。