Code
#include <bits/stdc++.h>
using namespace std;
void combine(vector<int> &a, int p, int q, int r) {
int n1 = q - p + 1;
int n2 = r - q;
vector<int> x(n1 + 1), y(n2 + 1);
for (int i = 0 ; i < n1 ; i ++) x[i] = a[p + i];
for (int i = 0 ; i < n2 ; i ++) y[i] = a[i + q + 1];
x[n1] = INFINITY;
y[n2] = INFINITY;
int i = 0, j = 0;
for (int k = p ; k < r ; k ++) {
if (x[i] <= y[j]) a[k] = x[i ++];
else a[k] = y[j ++];
}
}
void merge_sort(vector<int> &a, int p, int r) {
int q = (p + r) / 2;
merge_sort(a, p, q + 1);
merge_sort(a, q + 1, r);
combine(a, p, q, r);
}
int main() {
int n;
cin >> n;
vector<int> a(n);
for (int i = 0 ; i < n ; i ++) cin >> a[i];
merge_sort(a, 0, n);
for (int i = 0 ; i < n ; i ++) {
cout << a[i] << (i == n - 1 ? "\n" : " ");
}
return 0;
}
