分治法实现归并排序算法思想C++

分治法是一种常用的算法设计方法，它将一个大问题分解成若干个相同或类似的子问题，然后递归地解决这些子问题，最后将子问题的解合并起来得到原问题的解。归并排序就是一种使用分治法的排序算法。

归并排序的思想如下：
1. 将待排序的数组不断地二分，直到每个子数组只有一个元素。
2. 将相邻的两个子数组进行合并，合并时按照从小到大的顺序将元素放入一个临时数组中。
3. 重复步骤2，直到所有的子数组都合并成一个有序的数组。

以下是C++实现归并排序算法的代码示例：

// 合并两个有序数组
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++];
        }
    }

    // 将剩余的元素放入临时数组中
    while (i <= mid) {
        temp[k++] = nums[i++];
    }
    while (j <= right) {
        temp[k++] = nums[j++];
    }

    // 将临时数组中的元素复制回原数组
    for (int m = 0; m < k; m++) {
        nums[left + m] = temp[m];
    }
}

// 归并排序
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);  // 合并两个有序子数组
}

// 调用归并排序函数
vector<int> nums = {5, 2, 9, 1, 7};
mergeSort(nums, 0, nums.size() - 1);