题解

#include<iostream>
using namespace std;
int n , a[1010] , temp[1010];
void MergeSort(int l , int r)
{
	//2.1、递归的结束条件:只有一个数，就不用再递归下去，直接返回 
	if(l==r)     
        return ;
	//2.2、找到中间位置，递归处理左半部分，递归处理右半部分 
	int mid = (l + r) / 2;
	MergeSort(l,mid);
	MergeSort(mid+1,r);
	//3、合并，两个序列分别为[l,mid] 和 [mid+1,r]，从最左边开始，依次比较，小的数放入结果数组temp，下标右移 
	int i = l, j = mid + 1, k = l;
	while(i <=mid && j <= r)
	{
		if(a[i] <= a[j])
			temp[k++] = a[i++];
		else
			temp[k++] = a[j++];
	}
	//3.1、判断两个序列是否有剩余，有剩余的，全部放入结果数组 temp 
	while(i <= mid)
		temp[k++] = a[i++];
	while(j <= r)
		temp[k++] = a[j++];
	//4、把结果数组 temp 重新赋给 a 数组 
	for(int i=l;i<=r;i++)
		a[i]=temp[i];
	//5、输出a数组 
	for(int i = 1; i <= n; i++)
		cout << a[i] << " ";
	cout << endl;
}
int main()
{
	//1、定义变量 n 和数组 
	cin >> n;
	for(int i = 1; i <= n; i++)
		cin >> a[i];
	//2、划分，左端点为 1，右端点为 n，递归处理 
	MergeSort(1 , n);
	return 0;
}