[数据结构与算法]C++归并排序

C++归并排序

算法概述：
归并排序是将有序的两个数组进行排序，即将待排序的一个数组不断进行递归，直到递归成两个都只含有一个元素的数组，则对这两个之含有一个元素的数组进行排序，不断回溯，直到回溯到可以将待排序数组分成两个有序数组，之后对其进行最后一次有序数组排序，最后两个有序数组合并为一个有序数组，就得到了需要进行排序的数组，可以从小到大进行排序，也可以从大到小进行排序。

代码：

void mergeSort(vector<int>& nums, vector<int>& path, int left, int right)
{
//1.递归返回条件
	if(left >= right){
		return;
	}
	int mid = (left + right) / 2;
//2.进行左右数组递归
	mergeSort(nums, path, left, mid);//对左边数组进行递归
	mergeSort(nums, path, mid + 1, right);//对右边数组进行递归
//3.每个递归中需要进行的动作，即对两个有序的数组进行合并排序	
	int l = left;//第一个数组的起始位置
	int r = mid + 1;//第二个数组的起始位置
	
	for(int ix = left; ix <= right; ++ix)
	{
		path[ix] = nums[ix];
	}
	for(int ix = left; ix <= right; ++ix){
		if(ix == mid + 1){
			nums[ix] = path[ix];
		}else if(ix == right + 1 || path[left] <= path[right]){
			nums[ix] = path[left++];
		}else{
			nums[ix] = path[right++];
		}
	}
}

时间复杂度：O(nlog n);
空间复杂度：O(n);