[백준] 2751 수 정렬하기 2

[백준] 2751 수 정렬하기 2

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

#include <algorithm>
#include <vector>
#include <iostream>
using namespace std;

int n;
vector<int> vec;

void merge(int start1, int end1, int start2, int end2) {
	vector<int> sorted;
	int idx1 = start1;
	int idx2 = start2;

	while (idx1 <= end1 && idx2 <= end2) {
		if (vec[idx1] < vec[idx2]) {
			sorted.push_back(vec[idx1]);
			idx1++;
		}
		else {
			sorted.push_back(vec[idx2]);
			idx2++;
		}
	}

	while (idx1 <= end1) {
		sorted.push_back(vec[idx1]);
		idx1++;
	}
	while (idx2 <= end2) {
		sorted.push_back(vec[idx2]);
		idx2++;
	}

	for (int i = 0; i < sorted.size(); ++i) {
		vec[start1 + i] = sorted[i];
	}
	return;
}

void mergeSort(int start, int end) {
	//정렬하고자하는 배열의 길이 1
	if (end == start) {
		//no action
	}
	//정렬하고자하는 배열의 길이 2
	else if (end - start == 1) {
		if (vec[start] > vec[end]) swap(vec[start], vec[end]);
	}
	//정렬하고자하는 배열의 길이 2이상인 경우 쪼개기
	else {
		int mid = (end + start) / 2;
		mergeSort(start, mid);
		mergeSort(mid + 1, end);
		merge(start, mid, mid + 1, end);
	}
	return;
}



int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	cin >> n;

	int input;
	for (int i = 0; i < n; ++i) {
		cin >> input;
		vec.push_back(input);
	}

	//병합정렬
	mergeSort(0, n - 1);

	for (int i = 0; i < n; ++i) {
		cout << vec[i] << "\n";
	}
	return 0;
}