/递归把原数组不断划分，最后变成只含一个元素的数组
然后回溯，一个为 i 指针指向,一个为 j 指针指向,比较大小，放入tmp中,此时tmp数组有两个元素
同理可知，数组从1到2，2到4，4到8 ~ 一直到原数组长度/

include [HTML_REMOVED]

using namespace std;

const int N = 100010;
int q[N],temp[N];
int n;

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);//递归成只含一个元素的数组

int k = 0, i = l,j = mid + 1;
while(i <= mid && j <= r)//不是i < j，根据题意 i是一定小于j的 
{
    if(q[i] < q[j]) temp[k ++ ] = q[i ++ ];
    else temp[k ++ ] = q[j ++ ];
}

while(i <= mid) temp[k ++ ] = q[i ++ ];
while(j <= r)   temp[k ++ ] = q[j ++ ];

for(k = 0,i = l;i<=r;i++,k++) q[i] = temp[k];

}

int main()
{
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(false);
cin >> n;
for(int i = 0;i[HTML_REMOVED]> q[i];

merge_sort(q,0,n - 1);

for(int i = 0;i<n;i++) cout << q[i] << ' ';
return 0;

}