归并排序

// 归并排序
 void Merge1(int arr[], int p, int mid, int r)
 {
	 int n1 = mid - p + 1; @1
	 int n2 = r - mid;

	 int *pLeft = new int[n1](); @2
	 int *pRight = new int[n2]();
	 for (int i = 0; i < n1; ++i) @3
	 {
		 pLeft[i] = arr[i+p];
	 }
	 for (int j = 0; j < n2; ++j) @4
	 {
		 pRight[j] = arr[j+mid+1];
	 }
	 int i = 0, j = 0; @5
	 int k = p; @6
	 while (i < n1 && j < n2) @7
	 {
		 if (pLeft[i] <= pRight[j]) @8
		 {
			 arr[k++] = pLeft[i++];
		 }else
		 {
			 arr[k++] = pRight[j++];
		 }
	 }
	 while (i < n1) @9
	 {
		 arr[k++] = pLeft[i++];
	 }
	 while (j < n2) @10
	 {
		 arr[k++] = pRight[j++];
	 }
	 delete []pLeft; @11
	 delete []pRight;
 }

 void MegerSort(int arr[], int lhs, int rhs)
 {
	 if (lhs < rhs)
	 {
		 int mid = (lhs + rhs)/2;
		 MegerSort(arr, lhs, mid);
		 MegerSort(arr, mid+1, rhs);
		 Merge1(arr, lhs, mid, rhs);
	 }	 
 }

归并排序和快速排序一样，也是基于分治法的排序，其平均复杂度O（nlgn），属于稳定排序。

核心思路：把一个待排序的序列划分成两个子序列，然后再把子序列继续划分下去，直到子序列的长度为1或为空跳出递归，然后开始合并，最开始的归并是把两个元素合成一个长度为2的有序序列，然后再往外层跳转，合并成一个长度为4的有序序列。把两个有序的子序列合并成一个序列是关键

@1：先确定子序列的长度

@2：开启辅助空间，存放原始的待排序列

@3和@4：把两个子序列分别复制到辅助空间，这里要考虑边界问题

@5和@6：i记录的是左序列的当前位置，j记录的是右序列的当前位置，k记录的是目标数组的下一个待排序位置。

@7：两个子序列都从左往右移动，每一次比较i和j所指向的位置的元素，小的复制到目标序列中，然后位置更新。i的最大值是n1-1，j的最大值是n2-1

@8：小于等于号是维护稳定性的关键，因为是非递减序列，所以左侧子序列较小，右侧子序列较大，如果两个相等的话，先让左侧子序列的元素复制到目标数组，两个相同的元素的相对位置不会改变

@9和@10：如果i到达n1或是j到达n2，就跳出了@7循环，然后进入@9或@10循环，意味着某个子序列已经全部进入目标数组，另一个子序列可以直接复制过去，这在排两个有序链表的时候，直接把另一个链表的指针复制到目标链表就可以了，这里是数组，还要一个一个的复制。

@11：删除辅助空间

归并排序优化

void Merge2(int arr[], int p, int q, int r)
 {
	 int n1 = q - p + 1;
	 int n2 = r - q;

	 int *pLeft = new int[n1+1](); @1
	 int *pRight = new int[n2+1]();
	 for (int i = 0; i < n1; ++i)
	 {
		 pLeft[i] = arr[i+p];
	 }
	 for (int j = 0; j < n2; ++j)
	 {
		 pRight[j] = arr[j+q+1];
	 }
	 pLeft[n1] = 0xFFFFFF; @2
	 pRight[n2] = 0xFFFFFF;
	 int i = 0, j = 0;
	 for (int k = p; k <= r; ++k) @3
	 {
		 if (pLeft[i] <= pRight[j])
		 {
			 arr[k] = pLeft[i++]; @4
		 }else
		 {
			 arr[k] = pRight[j++]; @5
		 }
	 }

	 delete []pLeft;
	 delete []pRight;
 }

这个不以两个子序列的区间为循环控制条件，而是以整个目标数组的区间[p, r]为循环控制条件。

@1：开辟多余一个空间

@2：存放足够大的值

@3：同样i和j指向子序列的当前待排序元素 位置，而循环控制条件为[p, r]，因为任何一个子序列到达最后一个元素（也就是那个足够大的值位置）后，另外一个都不能大于它。假如左子序列先到达终点，则则判断条件始终会转向@5，进而把右子序列的剩余元素复制到目标数组；假如右子序列先到达终点，则判断条件始终转向@4。