[Sorting 03] Merge Sort의 개념 및 구현

들어가며

 

복잡한 정렬 알고리즘 중에서 가장 간단하다는 합병정렬(merge sort)에 대해 포스팅해 볼 것이다.
알고리즘을 막 공부하기 시작했을 때, merge sort를 구현하다가 막혀 며칠을 끙끙댔던 기억이 있다.
이제 그 때보다는 실력이 조금 나아졌으리라 기대하면서 포스팅을 시작해본다.

 

개념 및 특징

---

• 존 폰 노이만이 1945년에 개발했다.
• 분할정복(divide and conquer) 알고리즘 중 하나이다.
• 결과를 임시 배열에 저장했다가 다시 복사하는 과정이 발생하므로, 추가적인 메모리 공간도 요구되고 배열 복사에 시간이 소요된다.
• 최악 시간 복잡도: O(NlogN)
• 최선 시간 복잡도: O(NlogN)
• 평균 시간 복잡도: O(NlogN)

알고리즘

---

1. 리스트의 길이가 1 이하면 이미 정렬된 것으로 본다.
2. 분할(divide): 정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기를 가진 2개의 리스트로 나눈다.
3. 정복(conquer): 각 부분 리스트를 재귀적으로 merge sort를 수행한다.
4. 결합(combine): 나눠진 2개의 리스트를 다시 하나의 리스트로 합친다. 이 때 정렬 결과가 임시 배열에 저장되므로 추가적인 메모리 공간이 요구된다.
5. 복사(copy): 임시 배열에 저장된 결과를 원래 배열에 복사한다.

소스코드(C++)

---

앞서 설명한 것과 같이, merge sort는 결합(combine) 과정에서 임시 배열에 결과를 저장하므로 추가 메모리 공간이 요구된다. 추가 메모리 공간을 사용하기 싫어서 코드를 야메(?)로 작성했는데 정석적인 구현방법은 아닐 수 있다.

#include <iostream>
#include <vector>
#include <iterator>
#include <algorithm>

using namespace std;

typedef vector<int>::iterator IT;

void mergeSort(IT bit, IT eit)
{
	
	int dist = eit - bit;
	int mid = dist/2;
	
	if(dist < 2)
		return ;
		
	mergeSort(bit, bit+mid);
	mergeSort(bit+mid, eit);
	
	IT it1 = bit;
	IT it2 = bit+mid;
	
	while(it1 != it2) {
		if(*it1 < *it2) {
			it1++;
		}
		else {
			int tmp = *it1;
			*it1 = *it2;
			it1++;
			
			IT it;
			for(it=it2+1;it!=eit && !(*it >= tmp);++it)
				*(it-1) = *it;
			*(it-1) = tmp;	
		}		
	}
}

int main(void)
{
	int a[] = {6, 5, 4, 2, 4, 1};
	vector<int> vc(a, a+sizeof(a)/sizeof(a[0]));
	
	copy(vc.begin(), vc.end(), ostream_iterator<int>(cout," "));
	cout << endl;
	
	mergeSort(vc.begin(), vc.end());
	
	copy(vc.begin(), vc.end(), ostream_iterator<int>(cout," "));
	cout << endl;
	
	return 0;
}

관련문제 

---

• 백준 11728번: 배열 합치기(https://www.acmicpc.net/problem/11728) *