void merge(vector<int>& nums, int left, int mid, int right)
{
vector<int> tmp(right - left + 1); // 临时数组用于合并
int i = left, j = mid + 1, k = 0;
while (i <= mid && j <= right)
{
if (nums[i] <= nums[j]) tmp[k++] = nums[i++];
else tmp[k++] = nums[j++];
}
while (i <= mid) tmp[k++] = nums[i++];
while (j <= right) tmp[k++] = nums[j++];
for (int p = 0; p < k; p++)
{
nums[left + p] = tmp[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); // 合并两个有序子数组
}
在这个示例代码中,我们使用了分治法将数组分成两部分,对每一部分递归地进行归并排序,并最终合并两个有序子数组。时间复杂度为O(nlogn),空间复杂度为O(n)。