https://www.acmicpc.net/problem/2751
#include <iostream>
#include <vector>
using namespace std;
int N, arr[1000001];
int *sorted;
void merge(int left, int right)
{
int mid = (left + right) / 2;
int i = left;
int j = mid + 1;
int k = left;
while (i <= mid && j <= right)
{
if (arr[i] <= arr[j])
sorted[k++] = arr[i++];
else
sorted[k++] = arr[j++];
}
int temp = i > mid ? j : i;
while (k <= right)
sorted[k++] = arr[temp++];
for (int i = left; i <= right; i++)
arr[i] = sorted[i];
}
void partition(int left, int right)
{
int mid;
if (left < right)
{
mid = (left + right) / 2;
partition(left, mid);
partition(mid + 1, right);
merge(left, right);
}
}
int main()
{
int N;
cin >> N;
sorted = new int[N];
for (int i = 0; i < N; i++)
scanf("%d", &arr[i]);
partition(0, N - 1);
for (int i = 0; i < N; i++)
cout << arr[i] << '\n';
}