/归并排序，
把一堆数字从中间分开，
左右先排完序，然后两个指针从两边向右走，
如果左边的最小数字小于右边就把左边数字放进新的数组
反之放右边的数字
最后如果有哪边没有排完就直接放后面
/

include[HTML_REMOVED]

using namespace std;
const int N = 1e6 + 10;
int a[N], temp[N];

void merge_sort(int a[], int l, int r)
{
if (l >= r)return;
int mid = l + r >> 1;//相当于除以二
merge_sort(a, l, mid);
merge_sort(a, mid + 1, r);
int i = l, j = mid + 1,k=0;
while (i <= mid && j <= r)
{
if (a[i] <= a[j])temp[k] = a[i];
else temp[k] = a[j];
}
while (i <= mid)temp[k] = a[i];
while (j <= r)temp[k] = a[j];
for (i = l, k = 0; i <= r; i, k)a[i] = temp[k];
}
int main()
{
int n, i, j;
cin >> n;
for (i = 0; i < n; i)cin >> a[i];
merge_sort(a, 0, n - 1);
for (i = 0; i < n; i)cout << a[i]<<”\t”;
return 0;
}