[BOJ] 2751번 : 수 정렬하기 2

1. problem : 

https://www.acmicpc.net/problem/2751

 

2. solution 1 :

#include <bits/stdc++.h>
using namespace std;
int n;
int arr[1000005];
int tmp[2000005];

void merge(int st, int ed) {
	int mid = (st + ed) / 2; 
	int lidx = st;
	int ridx = mid; 
	for (int i = st; i < ed; i++) {
		if (lidx == mid) tmp[i] = arr[ridx++];
		else if (ridx == ed) tmp[i] = arr[lidx++];
		else if (arr[lidx] <= arr[ridx]) tmp[i] = arr[lidx++];
		else tmp[i] = arr[ridx++];
	}

	for (int i = st; i < ed; i++) {
		arr[i] = tmp[i];
	}
}
void merge_sort(int st, int ed) {
	if (st + 1 == ed) return;
	int mid = (st + ed) / 2;
	merge_sort(st, mid);
	merge_sort(mid, ed); 
	merge(st, ed);
}

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	for (int i = 0; i < n; i++) cin >> arr[i];

	merge_sort(0, n);
	for (int i = 0; i < n; i++) cout << arr[i] << '\n';

}