https://www.acmicpc.net/problem/2751
2751번: 수 정렬하기 2
첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.
www.acmicpc.net
#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';
}