Section 2.归并排序

一、中心思想：分治

1. 以中间点为界： mid=(l+r)/2
2. 递归排序分界点左边和右边
3. 归并——合二为一

二、核心内容：合二为一

1. 分界点左边从小到大排序：数组 a ，分界点右边从小到大排序：数组 b ，答案数组 ans
2. 指针 i ， j 分别指向 a 、 b 的第一个数，如果 i 指向的数比 j 指向的数小，则将 i 指向的数移至 ans ，指针 i 向后移动， j 指向的数比 i 指向的数小时同理。若 i 先到达末尾，则 j 及以后的数全部移至 ans ，若 j 先达到末尾同理

三、上代码！

void merge_sort(int q[], int l, int r)
{
	int tmp[1000010];
	if (l >= r)
		return;
	int mid = (l + r) / 2;
	merge_sort(q, l, mid);
	merge_sort(q, mid + 1, r);  //递归排序左半边和右半边
	int k = 0, i = l, j = mid + 1;  //k用来标记存了多少答案
	while (i <= mid && j <= r)
	{
		if (q[i] < q[j])
			tmp[k++] = q[i++];
		else
			tmp[k++] = q[j++];
	}                            //以上考虑的是两边指针都没到终点的情况
	while (i <= mid)
		tmp[k++] = q[i++];
	while (j <= r)
		tmp[k++] = q[j++];  //有一根指针到终点，将另一个指针后面的数转移到答案序列上
	for (i = l, j = 0; i <= r; i++, j++)  //将答案移回数组q
		q[i] = tmp[j];
}

四、配套练习

AcWing787

AcWing788