归并排序

需要额外空间的外部排序？

菜鸟教程版本

这个版本的写法很不一样，

1. 首先，它每次都copy构造了两个子数组，然后再从这两个子数组中挑元素往原数组放
2. 构造的两个子数组容量都+1，并且设置末尾值为max值，为了比较大小的时候方便

 // 合并操作
 void Merge(vector<int>& arr, int front, int mid, int end) {
	 // 这是个什么构造方式，是类似于传入一个vector，然后copy一份对吧
	 vector<int> LeftSubArr(arr.begin() + front, arr.begin() + mid + 1);// 左半部分数组，注意这里额外加了1
	 vector<int> RightSubArr(arr.begin() + mid + 1, arr.begin() + end + 1);// 右半部分数组，这里
	 // 左半部分的指针和右半部分的指针
	 int idxLeft = 0, idxRight = 0;
	 // 后面的意思是返回编译器允许的int最大值
	 // 在数组末尾插入int最大值？
	 LeftSubArr.insert(LeftSubArr.end(), numeric_limits<int>::max());
	 RightSubArr.insert(RightSubArr.end(), numeric_limits<int>::max());
	 // Pick min of LeftSubArray[idxLeft] and RightSubArray[idxRight], and put into Array[i]
	 for (int i = front; i <= end; i++) {
		 if (LeftSubArr[idxLeft] < RightSubArr[idxRight]) {
			 arr[i] = LeftSubArr[idxLeft];
			 idxLeft++;
		 }
		 else {
			 arr[i] = RightSubArr[idxRight];
			 idxRight++;
		 }
	 }
 }

 // 手写归并排序
 // 待排序的数组，待排序序列的起始下标、结束下标
 void MergeSort(vector<int>& arr, int front, int end) {
	 if (front >= end) return;// 当数组长度不合法或者数组长度为1时不理会
	 int mid = (front + end) / 2;
	 MergeSort(arr, front, mid);// 处理左半边
	 MergeSort(arr, front, mid);// 处理右半边
     Merge(arr, front, mid, end);
 }