什么是归并排序？

归并排序出自《算法导论》中分治法一章，他是为了解决数组排序问题而创造的算法，利用了递归的方式。

这是书上的伪代码实例：

这很好理解，就是把一个数组分成L和R两部分，然后再对各个部分继续细分，后把个个部分排序，最后合并。

接下来就用c++来实现一下：

void Merge(vector&A, int p, int q, int r) {
	int n1 = p - q;
	int n2 = r - q + 1;
	vector L;
	vector R;//创建两个数组
	for (int i = p; i < q; i++) {
		L.push_back(A[i]);
	}
	for (int i = q; i < r+1; i++) {
		R.push_back(A[i]);
	}
	L.push_back(INT_MAX);//以防超出范围
	R.push_back(INT_MAX);
  //比较，排序
	int i = 0;
	int j = 0;
	for (int k = p; k < r + 1; k++) {
		if (L[i] < R[j]) { A[k] = L[i]; i++;}
		else { A[k] = R[j]; j++; }
	}
}
//利用递归
void MergeSort(vector&A,int p,int r) {
	if (r - p > 1) {
		int q = (r + p + 1) / 2;
		MergeSort(A, p, q);
		MergeSort(A, q, r);
		Merge(A, p, q, r);
	}
}
//尝试一下
int main() {
	//                          p        q       r       
	//                          |         |        |        
	vectora = { 2,1,3,4,1,2,4,5 };
	MergeSort(a, 0, 7);
  for (int i : a) {
		cout << i;
	}
}

他书上给的实例是默认数组的第一个值为1，但是我们所有的语言第一个值都是0，所以我们的代码和他给的代码有所不同。

我们看这段代码的时候要利用递归的思想，我们知道编译器会按照顺序执行我们的指令，所以他这个分治的过程不是同时进行的而是在一个个分治到最小的时候开始返回，寻找下一个分治节点。

所以上面的例子中会这样执行（先上后下）：

{2，1，3，4，1，2，4，5} ---> {1,2,4,5} -->{1,2} || {4,5} --> {1} || {2} --> {1,2} || {4,5} --> {2,1,3,4} || {1,2,4,5} --> {2,1} || {3,4} --> {2} || {1} --> {1,2} || {3,4} -->{1,2,3,4} || --> {1,2,4,5} -->

{1 ,1 ,2 ,2 ,3 ,4 ,4 ,5 }

大家学会了吗，如果对你的学习有帮助的话给我点个赞把！