[알고리즘] 정렬(5) - 병합 정렬(Merge Sort)

 원리 

1. 정렬할 배열을 사이즈가 1이 될때까지 반으로 나눈다. (분할)

2. 나눌 수 없을때까지 나눈뒤 정렬을 한다. (정복)

3. 정렬 한 결과를 병합한다. (병합)

 

[ 16, 11, 6, 19, 12, 2, 2, 10 ]

정렬하기에 앞서 분할 정복(Divide and conquer)을 이해하고 있어야합니다. 모르더라도 이번 기회에 직접 이해해 보도록 하겠습니다.

 

배열을 절반으로 분할

정렬(정복)후 병합

분할은 배열을 절반씩 나누어서 사이즈가 1이 될때까지 나눈 것입니다. 그리고 정렬을 하고 병합을 하는 식으로 구성되어있습니다. 방식은 쉽게 이해하실 수 있습니다. 그렇다면 왜 굳이 분할을 해서 다시 합치면서 정렬을 해야할까요? 이는 아래 시간복잡도를 알아보면서 이해해보도록 하겠습니다.

 구현 

template<typename T>
vector<T> MergeSort(const vector<T>& data)
{
	if (data.size() == 1) return data;
	int mid = data.size() / 2;

	const vector<T> left = MergeSort(vector<T>(data.begin(), data.begin() + mid));
	const vector<T> right = MergeSort(vector<T>(data.begin() + mid, data.end()));

	return merge(left, right);
}

다음은 분할 하는 코드입니다. Top-Down방식으로 구현을해서 직관적으로 left 변수와 right 변수를 나눌 수 있습니다.

 

위에서 나오는 배열로 예를 들어보면 원 배열 [16 11 6 19 12 2 2 10] 에서 변수 left 는 [16 11 6 19]에 대한 함수를 호출하고 변수 right는 [12 2 2 10]에 대한 함수를 호출합니다. 호출된 [16 11 6 19]에서 또 다시  left [16 11] 과 right[6 19] 호출 ... 반복해서 사이즈가 1이 되는 순간 재귀를 종료하고 그때부터 merge(병합)이 시작됩니다. 그렇다면 merge 함수에서는 당연히 정렬과 병합이 이루어져야 겠죠?

 

https://imgur.com/

 

template<typename T>
vector<T> merge(const vector<T>& left, const vector<T>& right)
{
	int lsize = left.size(), rsize = right.size();
	int lidx = 0, ridx = 0, idx = 0;
        vector<T> result(lsize + rsize);
    
	for (; lidx != lsize && ridx != rsize; ++idx)
		result[idx] = left[lidx] < right[ridx] ? left[lidx++] : right[ridx++];
	for (; lidx != lsize; ++idx) result[idx] = left[lidx++];
	for (; ridx != rsize; ++idx) result[idx] = right[ridx++];
    
	return result;
}

merge를 하기전에 미리 공간에 대해서 reserve를 해줍시다. push_back()로도 가능하지만 매번 capacity를 2배씩 늘려주는 연산은 불필요합니다. 정렬을 하면서 병합을 하는 과정은 비교적 간단합니다. left 배열과 right 배열의 원소를 앞에서부터 서로 비교하면서 오름차순 또는 내림차순으로 순서를 정할 수 있습니다.

 

left나 right의 원소를 모두 병합시켰다면 나머지 한쪽의 원소들을 연속으로 병합시켜 줍니다. 이유는 left와 right는 이미 정렬된 상태에서 넘어오기 때문입니다.

 

병합정렬은 병합과정에서 특징이 있는데, 만약 배열로 구현을 하려면 별도 저장 공간이 필요하게됩니다. 반면에 연결리스트(linked list)를 사용한다면 in-place sort가 가능하게 됩니다. 포인터를 통해 가리키는 주소값만 바꿔주면 되기 때문입니다.

 시간복잡도 

잘 알려진 과정으로 시간복잡도를 구해보면, 이분탐색 O(logN)의 시간복잡도를 가집니다. 그리고 Merge()에서 단순히 나열을 하고 있기 때문에 O(N)의 시간복잡도를 가지고 결과적으로 O(NlongN)의 시간 복잡도를 가지게 됩니다. 직접 수를 나열해서 위 복잡도를 증명해보겠습니다.

 

https://imgur.com/

 

즉 원소의 개수 8개일 때, 8 -> 4 -> 2 -> 1 순으로 나눌 수 있습니다. 반면에 배열의 개수는 1 -> 2 -> 4 -> 8 으로 증가하므로  [8 * 1 = 8 ] [4 * 2 = 8] [2 * 4 = 8] [1 * 8 = 8] 이고, 모두 8번 비교하게 됩니다. 즉, [8 * n/2 1쌍] [4 * n/2 2쌍] [2 * n/2 3쌍] [1 * n/2 4쌍] 순으로 진행됩니다. 따라서 O(n * logn)의 시간복잡도를 가지게됩니다.

 

이를 일반화 하면 2^(진행 횟수) = 배열의 개수(나뉜 개수)

2^3 = 8 --> 2^k = n --> k = logn --> O(logn) 이고,

또한 각 단계마다 리스트의 전체를 순회하기때문에 O(n), 따라서 총 O(nlogn)이 됩니다! 

 

이렇게 분할해서 정복을하게되면 시간복잡도를 줄일 수 있기때문에 자주 사용되는 기법입니다. 기회가 된다면 분할정복에 대해서도 포스팅할 계획입니다.

 

 정리 

이름	BEST	AVG	WORST	RUN TIME(정수 60,000)
버블 정렬	n^2	n^2	n^2	확인
선택 정렬	n^2	n^2	n^2	확인
삽입 정렬	n	n^2	n^2	확인
계수 정렬	n	n	n	확인
병합 정렬	nlogn	nlogn	nlogn	사진 참고

병합 정렬 런타임(랜덤 정수 60,000개)

약 70ms ~ 90ms가 측정된 것을 확인할 수 있습니다.

 

실행 환경 :

- windows 10 WSL2 - ubuntu 18.04

- gcc 7.4.0

- cpu : i3

- ram : 8G

 참조 

- 위키백과

합병 정렬 - 위키백과, 우리 모두의 백과사전

- https://ratsgo.github.io/data%20structure&algorithm/2017/10/03/mergesort/