[백준] 2751번 수 정렬하기2 (병합정렬)

-문제

 

-코드

#include<stdio.h>
#include<vector>
using namespace std;

vector<int> a;
vector<int> tmp;

void divide(int lt, int rt)
{
	int mid, p1, p2, p3;
	if (lt<rt)
	{
		mid = (lt + rt) / 2;
		divide(lt, mid);
		divide(mid + 1, rt);
		p1 = lt;
		p2 = mid + 1;
		p3 = lt;
		while (p1<=mid && p2<=rt)
		{
			if (a[p1] < a[p2]) tmp[p3++] = a[p1++];
			else tmp[p3++] = a[p2++];
		}
		while(p1<=mid) tmp[p3++] = a[p1++];
		while(p2<=rt) tmp[p3++] = a[p2++];

		for (int i = lt; i <= rt; i++)
		{
			a[i] = tmp[i];
		}
	}
}

int main()
{
	int n, k;
	scanf("%d", &n);
	for (int i = 0; i < n; i++)
	{
		scanf("%d", &k);
		a.push_back(k);
		tmp.push_back(0);
	}

	divide(0,n-1);

	for (int i = 0; i < n; i++)
	{
		printf("%d\n", a[i]);
	}

	return 0;
}