Q.19

#include <iostream>
#include <vector>
using namespace std;

vector<int> tmp, a;

void solve(int l, int r) {
    if (l >= r)
        return;
    int m = (l + r) / 2;
    solve(l, m);
    solve(m + 1, r);
    int i = l, j = m + 1, cur = l;
    while (i <= m && j <= r)
        if (a[i] < a[j])
            tmp[cur] = a[i], i++, cur++;
        else
            tmp[cur] = a[j], j++, cur++;
    while (i <= m)
        tmp[cur] = a[i], i++, cur++;
    while (j <= r)
        tmp[cur] = a[j], j++, cur++;
    for (int i = l; i <= r; i++)
        a[i] = tmp[i];
}

int main()
{
    int n;
    cin >> n;
    a.resize(n);
    tmp.resize(n);
    for (int i = 0; i < n; i++)
        cin >> a[i];
    solve(0, n - 1);
    for (int i = 0; i < n; i++)
        cout << a[i] << ' ';
    return 0;
}