백준 2751

Merge Sort 구현

#include<iostream>	
using namespace std;

int n;
int arr[1000005];
int tmp[1000005];

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

void mergeSort(int st, int ed) {
	// ex) 길이가 2인 정렬되지 않은 배열이 주어짐
		// 1. 길이가 1이 되도록 분할(반으로 계속 쪼갬)
	if (st + 1 == ed) return;
	int mid = (st + ed) / 2; // 1
	mergeSort(st, mid); // (0,1)
	mergeSort(mid, ed); // (1,2)
	merge(st, ed); // 길이가 1인 리스트 2개를 길이가 2인 배열 하나로 합침
}

int main(void) {
	ios_base::sync_with_stdio(0);
	cin.tie(0);		
	cin >> n;
	for (int i = 0; i < n; i++) cin >> arr[i];	
	mergeSort(0, n);
	for (int i = 0; i < n; i++) {
		cout << arr[i] << '\n';
	}
	return 0;
}