记录编号	183198	评测结果	AAAAAAATTA
题目名称	排序测试	最终得分	80
用户昵称	吃蛋挞	是否通过	未通过
代码语言	C++	运行时间	11.168 s
提交时间	2015-08-30 11:02:13	内存使用	0.22 MiB

#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
void Merge_Sort(int,int);
void Merge(int,int);
int n;
vector<int>A;
int main()
{
	freopen("sorttest.in","r",stdin);
	freopen("sorttest.out","w",stdout);
	ios::sync_with_stdio(false);
	int i;
	cin>>n;
	A.resize(n);
	for(i=0;i<n;i++)
		cin>>A[i];
	Merge_Sort(0,n-1);
	for(i=0;i<n;i++)
		cout<<A[i]<<' ';
	return 0;
}
void Merge_Sort(int L,int R)
{
	if(L==R)return;
	else
	{
		int Mid=(L+R)/2;
		Merge_Sort(L,Mid);
		Merge_Sort(Mid+1,R);
		Merge(L,R);
	}
}
void Merge(int L,int R)
{
	int Mid=(L+R)/2,i=L,j=Mid+1;
	vector<int>Cup;
	while(i<=Mid||j<=R)
	{
		if(i>Mid)
		{
			Cup.push_back(A[j]);
			j++;
		}
		else 
		{
			if(j>R)
			{
			    Cup.push_back(A[i]);
			    i++;
		    }
			else
			{
				if(A[i]<A[j])
	    	    {
			        Cup.push_back(A[i]);
			        i++;
			    }
		        else
				{
			        Cup.push_back(A[j]);
					j++;
				}
			}
		}
	}
	for(i=L;i<=R;i++)
		A[i]=Cup[i-L];
}