1177-归并排序.cpp

/**************************************************************
 * Problem: 1177-¹é²¢ÅÅÐò
 * Author: Vanilla_chan
 * Date: 20210309
**************************************************************/
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<map>
#include<set>
#include<queue>
#include<vector>
#include<limits.h>
#define IL inline
#define re register
#define LL long long
#define ULL unsigned long long
#ifdef TH
#define debug printf("Now is %d\n",__LINE__);
#else
#define debug 
#endif
#ifdef ONLINE_JUDGE
char buf[1<<23],* p1=buf,* p2=buf,obuf[1<<23],* O=obuf;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
#endif
using namespace std;

template<class T>inline void read(T& x)
{
	char ch=getchar();
	int fu;
	while(!isdigit(ch)&&ch!='-') ch=getchar();
	if(ch=='-') fu=-1,ch=getchar();
	x=ch-'0';ch=getchar();
	while(isdigit(ch)) { x=x*10+ch-'0';ch=getchar(); }
	x*=fu;
}
inline int read()
{
	int x=0,fu=1;
	char ch=getchar();
	while(!isdigit(ch)&&ch!='-') ch=getchar();
	if(ch=='-') fu=-1,ch=getchar();
	x=ch-'0';ch=getchar();
	while(isdigit(ch)) { x=x*10+ch-'0';ch=getchar(); }
	return x*fu;
}
int G[55];
template<class T>inline void write(T x)
{
	int g=0;
	if(x<0) x=-x,putchar('-');
	do { G[++g]=x%10;x/=10; } while(x);
	for(int i=g;i>=1;--i)putchar('0'+G[i]);putchar('\n');
}
vector<int>sort(vector<int>a)
{
	if(a.size()==1||a.size()==0) return a;
	if(a.size()==2)
	{
		if(a[0]>a[1]) swap(a[0],a[1]);
		return a;
	}
	vector<int>x,y;
	int mid=a.size()/2;
	x.insert(x.begin(),a.begin(),a.begin()+mid);
	y.insert(y.begin(),a.begin()+mid,a.end());
	x=sort(x);
	y=sort(y);
	a.clear();
	int i=0,j=0;
	while(i<x.size()||j<y.size())
	{
		if(i>=x.size()) a.push_back(y[j]),j++;
		else if(j>=y.size()) a.push_back(x[i]),i++;
		else
		{
			if(x[i]<y[j]) a.push_back(x[i]),i++;
			else a.push_back(y[j]),j++;
		}
	}
	return a;
}
int n;
vector<int>ans;
int main()
{
	n=read();
	while(n--) ans.push_back(read());
	ans=sort(ans);
	for(int i=0;i<ans.size();i++) cout<<ans[i]<<" ";
	return 0;
}