머지 소트(Merge Sort) STL 없이 구현

퀵 소트와 마찬가지로 면접에서 자주 나오는 문제이므로 익혀두면 좋습니다.

	#include <iostream>
	#include <vector>
	using namespace std;
	const int MAX = 1000000 + 1;
	vector<int> v(MAX, 0);
	vector<int> temp(MAX, 0);
	// [begin, end)
	void mergeSort(int begin, int end)
	{
	if (end - begin == 1)
	{
	return;
	}
	if (end - begin == 2)
	{
	if (v[begin] > v[end - 1])
	{
	swap(v[begin], v[end - 1]);
	}
	return;
	}
	int mid = (begin + end) / 2;
	mergeSort(begin, mid);
	mergeSort(mid, end);
	merge(begin, end);
	}
	// 전제 조건: v[begin, mid), v[mid, end)는 이미 정렬이 되어있는 상태
	void merge(int begin, int end)
	{
	int mid = (begin + end) / 2;
	int idx = begin;
	int idx1 = begin;
	int idx2 = mid;
	while (idx1 < mid && idx2 < end)
	{
	temp[idx++] = (v[idx1] < v[idx2] ? v[idx1++] : v[idx2++]);
	}
	while (idx1 < mid)
	{
	temp[idx++] = v[idx1++];
	}
	while (idx2 < end)
	{
	temp[idx++] = v[idx2++];
	}
	for (int i = begin; i < end; i++)
	{
	v[i] = temp[i];
	}
	}

view raw .cpp hosted with ❤ by GitHub