记录编号	343465	评测结果	AAAAAATAAA
题目名称	排序测试	最终得分	90
用户昵称	king'back	是否通过	未通过
代码语言	C++	运行时间	10.875 s
提交时间	2016-11-09 11:33:08	内存使用	30.83 MiB

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

const int maxn=2000000+10;
long long a[maxn],b[maxn];
int n;
void merge(int l,int r);
void mergesort(int l,int mid,int r);
int main()
{
	freopen ("sorttest.in","r",stdin);
	freopen ("sorttest.out","w",stdout);
	
	scanf("%d",&n);
	for (int i=1; i<=n; i++)
		scanf("%d",&a[i]);
	merge(1,n);
	for (int i=1; i<n; i++)
		printf("%d ",a[i]);
	printf("%d\n",a[n]);
	return 0;
}
void merge(int l,int r)
{
	if (l==r) return;
	int mid=(l+r)/2;
	merge(l,mid);
	merge(mid+1,r);
	mergesort(l,mid,r);
}
void mergesort(int l,int mid,int r)
{
	int i=l,j=mid+1,len=l;
	while (i<=mid && j<=r)
	{
		if (a[i]<a[j])
		{
			b[len]=a[i];len++;i++;
		}
		else
		{
			b[len]=a[j];len++;j++; 
		}
	}
	while (i<=mid)
	{
		b[len]=a[i]; len++; i++;
	}
	while (j<=r)
	{
		b[len]=a[j]; len++; j++; 
	}
	for (int k=l; k<=r; k++)
		a[k]=b[k];
}