[알고리즘] 병합정렬 Merge Sort (C++ 구현)

📌 병합정렬

병합정렬은 오름차순으로 정렬된 두 리스트 A, B의 병합으로 정렬해나가는 방식이다. 병합정렬은 대표적인 분할정복기법(Divide-and-Conquer) 중 하나로 문제를 작은 단위로 쪼개서 풀어나가는 방식이다. 분할정복기법을 사용한 정렬 알고리즘에는 병합정렬, 퀵정렬이 있다.

 

병합정렬에서 중요한 아이디어는 

주어진 리스트를 일단 반으로 자르고 나중에 합치자는 것이다. 다음과 같은 두 가지 단계로 생각해볼 수 있다.

 

1) 분할정복기법에 맞게 병합정렬도 주어진 리스트를 원소 1인 리스트 여러 개로 쪼개지도록 자른다. 자르는 기준은 이진분할이다.

2) 모두 다 분할하여 주어진 원본 리스트의 길이 N만큼의 각 원소 리스트가 생성된다. 이 각 원소를 하나의 리스트로 간주하여 두 개씩 병합해 나가며 순차적으로 정렬한다.

 

mergesort

먼저 주어진 리스트를 크기 1의 원소 리스트로 모두 분할해야 한다. 주어진 리스트가 들어오면 분할지점(middle)을 계산해 left, right 2개로 나누어 리스트를 다시 구성한다. 이 리스트를 각각 정렬해서 다시 합쳐야 하는데, 이때 필요한 것이 정렬하면서 병합하는 함수(merge)이다.

 

mergesort 함수로 split이 끝날 때까지 split하면 각 리스트는 원소를 하나 가지므로 모두 정렬된 상태라고 볼 수 있다. 이때 리스트를 2개씩 묶어 합쳐 정렬해 새롭게 정렬된 크기 2짜리 리스트를 만든다. 즉, 아래 그림에서 [6], [5] 리스트 두 개를 [5, 6] 으로 정렬된 새 리스트를 만든다. 마찬가지로 남은 리스트에 대해 2개씩 묶어 병합하며 새로운 정렬된 리스트를 만들어 나간 결과 [5, 6], [2, 7], [3, 1], [4, 8] 의 결과를 얻는다.

vector<int> mergesort(vector<int> L) {
	if (L.size() == 1) {
		return L;
	}

	// 분할 지점(mid) 정해서 left, right로 split
	int mid = L.size() / 2;

	vector<int> left, right;
	for (int i = 0; i < mid; i++) {
		left.push_back(L[i]);
	}
	for (int i = mid; i < L.size(); i++) {
		right.push_back(L[i]);
	}

	// left와 right vector 각각 정렬해서 다시 합치기
	vector<int> result = merge(mergesort(left), mergesort(right));
	return result;
}

전공으로 들었던 알고리즘 ㅇㅇㅂ 교수님의 강의자료의 알고리즘을 참고해 구현했습니다. 교수님의 천재적 발상에 감탄하며 참고했습니다.. 추후 문제가 된다면 삭제할게요..

merge

이때 병합할 두 리스트를 각각 A, B (또는 Left, Right) 가 함수로 들어오면

간단하게 A가 비어있다면 B를, B가 비어있다면 A를 리턴하면 된다. 그렇지 않고 A와 B에 둘 다 원소가 들어있다면 첫번째 원소(A[0], B[0])를 비교해 더 작은 값을 새로운 정렬리스트의 첫번째 값으로 push 해준다. 그리고 남은 A, B의 원소들에 대해 재귀적으로 이 과정을 반복하면 새롭게 정렬된 리스트를 얻을 수 있다. 

vector<int> merge(vector<int> a, vector<int> b) {
	if (a.size() == 0)
		return b;
	if (b.size() == 0)
		return a;
	
	// 재귀적 병합과정
	if (a[0] < b[0]) {
		vector<int> target;
		target.push_back(a[0]);
		a.erase(a.begin());
		vector<int> p = merge(a, b);
		target.insert(end(target), begin(p), end(p));
		return target;
	}
	else {
		vector<int> target;
		target.push_back(b[0]);
		b.erase(b.begin());
		vector<int> p = merge(a, b);
		target.insert(end(target),	begin(p), end(p));
		return target;
	}
}

 

📌 시간복잡도

병합정렬의 시간복잡도는 nlogn으로 앞서 다뤘던 삽입, 버블 정렬의 n^2 보다 훨씬 효율적이다. 이진탐색이나 이진병합 등 '이진(binary)'이 들어가면 모두 logn 시간으로 계산된다. 실제 각 원소마다 정렬하는 데 드는 시간은 '1' 시간(1번만 비교하면 됨)이므로 총n시간이 든다(n번 비교하니까). 이에 따라 n log n 시간으로 시간복잡도를 계산할 수 있다. 

• 두 리스트 병합의 최적 시간복잡도 : 두 리스트가 서로 교차되는 부분이 없을 때 n/2
• 두 리스트 병합의 최악 시간복잡도 : 두 리스트가 서로 모두 교차할 때 n
• 공간복잡도 : A, B를 모두 복사하는 경우 2n 공간 차지 (linked-list 연결리스트로 구현하면 n으로 단축가능)