merge_sort

include <iostream>

using namespace std;

const int N = 1e6 + 10;

int p[N],temp[N];  //需要一个temp数组暂时存放数

void merge_sort(int q[], int l, int r)
{
	if (l >= r) return;

	int mid = (l + r) >> 1;

	merge_sort(q, l, mid);
	merge_sort(q, mid + 1, r);
    //递归处理左右两边的值，使得mid左右两边变成有序序列

	int i=l, j = mid + 1, cnt = 0;

	while (i <= mid && j <= r)
	{
		if (p[i] <= p[j]) temp[cnt++] = p[i++];
		else temp[cnt++] = p[j++];
        //哪个数的值小就取出来放入temp数组中
	}

	while (i <= mid) temp[cnt++] = p[i++];
	while (j <= r) temp[cnt++] = p[j++];
 //其中肯定有i或者j没有遍历完，把没有遍历完的数放入temp数组中
//（因为letf与right是有序的，所以最后留下来的数肯定比之前遍历好的数大，不然不会没有遍历完）

	for (int i = l,cnt=0; i <=r; i++,cnt++) p[i] = temp[cnt];
    //将temp中的数存入原数组p中
}

int main()
{
	int n,i;

	scanf_s("%d", &n);

	for (i = 0; i < n; i++)
	{
		scanf_s("%d", &p[i]);
	}

	merge_sort(p, 0, n - 1);

	for (i = 0; i < n; i++) {
		printf("%d ", p[i]);//最后遍历输出
	}

	return 0;
}