머지소트

#include <iostream>
using namespace std;
const int MAX = 1e5;

int n, a[MAX], b[MAX];

void msort(int st, int en) {
	if (st == en)
		return;

	int mid = (st + en) / 2;
	msort(st, mid);
	msort(mid + 1, en);

	int i = st, j = mid + 1, k = 0;
	while (i <= mid && j <= en) {
		if (a[i] > a[j]) b[k++] = a[j++];
		else b[k++] = a[i++];
	}
	while (i <= mid) b[k++] = a[i++];
	while (j <= en) b[k++] = a[j++];

	for (int i = st; i <= en; i++)
		a[i] = b[i - st];
}

int main() {
	cin >> n;
	for (int i = 0; i < n; i++) cin >> a[i];
	msort(0, n - 1);
	for (int i = 0; i < n; i++) cout << a[i] <<" ";
	cout << '\n';
}