병합 정렬 (Merge Sort)

● 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
using ll = long long;
using ii = pair<int, int>;
vector<int>arr(1000000);
vector<int>temp(1000000);
void mergesort(int start, int end); // 분할
void merge(int start, int mid, int end); // 정복

int main()
{
	// 입력
	int N;
	cin >> N;
	for (int i = 0; i < N; i++)
		cin >> arr[i];

	// 병합 정렬
	mergesort(0, N - 1);

	// 출력
	for (int i = 0; i < N; i++)
		cout << arr[i] << "\n";
	return 0;
}

void mergesort(int start, int end)
{
	if (start < end)
	{
		int mid = (start + end) / 2;
		mergesort(start, mid);
		mergesort(mid + 1, end);
		merge(start, mid, end);
	}
}

void merge(int start, int mid, int end)
{
	for (int i = start; i <= end; i++)
		temp[i] = arr[i];

	int left = start;
	int right = mid + 1;
	int idx = start;

	while (left <= mid && right <= end)
	{
		if (temp[left] < temp[right])
			arr[idx++] = temp[left++];
		else
			arr[idx++] = temp[right++];
	}

	if (left <= mid)
	{
		for (int i = left; i <= mid; i++)
			arr[idx++] = temp[i];
	}
	else
	{
		for (int i = right; i <= end; i++)
			arr[idx++] = temp[i];
	}
}

 

● 결과 화면

 

● 시간복잡도 : O(N long N)

 

● BOJ 문제 : 수 정렬하기 2

2751번: 수 정렬하기 2