[알고리즘] 정렬 - 병합 정렬, O(NlogN)

  병합 정렬은 문제를 더 작은 문제로 쪼개서 재귀적으로 풀이한다. 대표적인 O(NlogN) 정렬 알고리즘이다. 

 

    병합 정렬 (Merge Sort) 소개              

  기본적인 아이디어는 데이터를 절반으로 나눠서 전반부와 후반부를 각각 정렬해서 합치는 방식을 재귀적으로 반복하는 방식이다. 그래서 재귀호출하는 MergeSort 부분과 정렬된 두 데이터를 합치는 Merge 부분으로 나뉜다.

병합 정렬 과정 도식

 

  최종적으로 원소가 1개 남게 될 때 까지 계속 문제를 쪼갠 뒤, Merge(병합) 과정에서 순서에 맞게 데이터를 정렬하면서 두 데이터 그룹을 합치는 과정이 반복된다. 예를 들어 위 그림에서 1과 3으로 나뉘어졌다면 [1,3]으로 합쳐지고, 5와 2로 나뉘어졌다면 [2,5]로 합쳐진다. [1,3]과 [2,5]를 또 합치게 된다면 각각의 데이터에서 원소를 1개씩 차례대로 보면서 [1,2,3,5]의 순으로 정렬된 상태로 데이터가 합쳐진다. 아래 도식에서 구체적인 과정을 확인할 수 있다. M/2개의 데이터 2개를 합치는 과정은 최대 M-1번 (모든 원소를 1번씩 비교하는 경우), 최소 M/2 번 (한 쪽의 데이터가 모두 다른 한쪽의 데이터의 최소값보다 작거나 최대값보다 커서 몰려있는 경우 = 모두 정렬되어 있는 경우)의 비교가 이루어지므로 O(M)의 시간 복잡도를 가진다.

 

Merge 과정 도식

 

  병합 정렬의 시간 복잡도를 계산해보자. 우선 데이터를 2개로 쪼개서 원소 1개씩 남을 때까지 반복한다고 했으므로 총 log N 단계가 생긴다. 각 단계마다 Merge 과정이 반복되는데, 각 단계마다 존재하는 모든 Merge 과정을 합치면 최종적으로 O(N)의 시간복잡도를 가지므로 O(N)의 연산이 logN번 이루어지는 것이다. 따라서 최종적인 시간 복잡도는 O(NlogN)이 된다. 

 

  글로 설명하려니까 어렵다..

 

    C++ 구현              

#include <iostream>
#include <vector>
using std::vector;


vector<int> Merge(vector<int>& _arr, int _start, int _mid, int _end)
{
	int p0 = 0;
	int p1 = _start;
	int p2 = _mid + 1;

	vector<int> tempVec(_end - _start + 1, 0);

	while (p1 <= _mid && p2 <= _end)
	{
		if (_arr[p1] <= _arr[p2])
			tempVec[p0++] = _arr[p1++];
		else
			tempVec[p0++] = _arr[p2++];
			
	}

	while (p1 <= _mid)
	{
		tempVec[p0++] = _arr[p1++];
	}

	while (p2 <= _end)
	{
		tempVec[p0++] = _arr[p2++];
	}

	return tempVec;
}

void MergeSort(vector<int>& _arr, int _start, int _end)
{
	if (_start == _end)
		return;

	int mid = (_start + _end) / 2;

	MergeSort(_arr, _start, mid);
	MergeSort(_arr, mid + 1, _end);

	vector<int> tempVec = Merge(_arr,_start,mid,_end);

	for (int i = 0; i < tempVec.size(); ++i)
	{
		_arr[_start + i] = tempVec[i];
	}
}

int main()
{
	vector<int> arr = { 5,1,2,3,9,8,4,6,10,7 };
	MergeSort(arr, 0, arr.size() - 1);

	return 0;
}

 

  실제로 구현하다 보니 생각보다 애를 먹었다. MergeSort를 구현하다보니 Merge 과정에서 합친 데이터를 담을 별도의 공간이 필요했다. 여태까지 정리한 O(N^2) 정렬 알고리즘들은 space complexity는 O(1)이었는데 이러한 부분에서 차이가 존재했다. 여기서 구현할 때는 MergeSort에서는 원본 배열을 받아서 재귀호출해서 Merge의 결과로 받은 별도의 배열의 값을 복사해서 원본에 붙여넣는 식으로 구현했다.