void merge(vector<int> &data, int start, int mid, int end)//将两个有序数组data[start,..mid]和data[mid+1,..,end]合并
{
//int *temp=new(nothrow) int[end-start+1];
//if(!temp)
//{ //内存分配失败
// cout<<"error";
// return;
// }
vector<int> temp(end-start+1);
int i = mid, j = end, k = end-start;//从后向前，大的放在temp中，注意k的起始位置
while (i>=start&&j>=mid+1)
{
if (data[i]>=data[j])
{
temp[k--] = data[i--];
}
else
{
temp[k--]=data[j--];
}
}
while (i>=start)//当其中一个数组完成后将另一个数组复制
{
temp[k--] = data[i--];
}
while (j>=mid+1)
{
temp[k--] = data[j--];
}
for (int i = start,k=0; i <= end; i++,k++)
{
data[i] = temp[k];
}
//delete []temp;
}
void mergesort(vector<int> &data, int start, int end)
{
if (start<end)
{
int mid = (start+end)/2;
mergesort(data, start, mid);
mergesort(data, mid+1,end);
merge(data, start, mid, end);
}
}
int main()
{
int n;
while (cin>>n)
{
vector<int>data(n);
for (int i = 0; i < n; i++)
{
cin>>data[i];
}
int start = 0,end = n-1;
mergesort(data,start,end);
cout<<data[0];
for (int i = 1; i < n; i++)
{
cout<<" "<<data[i];
}
}
return 0;
}
