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

 

 

 

 

 

알고리즘 개요 및 소개

Merge Sort Animation

합병 정렬 또는 병합 정렬(Merge Sort)은 O(NlogN)의 시간 복잡도를 가지는 비교 기반(하나의 추상적인 비교 동작을 통해 목록 요소들을 읽어내는 정렬 알고리즘의 일종) 정렬 알고리즘이다. 일반적으로 구현했을 때 이 정렬을 안정 정렬에 속하며, 분할 정복 알고리즘의 하나이며 존 폰 노이만이 1945년에 개발했다.

시간 복잡도	O(NlogN)
장점	Quick Sort 와 다르게 Pivot이 없으며 무조건 반으로 나눠서 정렬하기 때문에 Pivot 위치에 따른 성능의 변화가 없다
단점	추가 메모리 사용의 단점이 있다 이러한 단점을 극복한 힙 정렬이 존재한다.

소스코드

#include<iostream>
constexpr int MAX_LIST = 10;
int tempArray[MAX_LIST];
void MergeSort(int* list, int begin, int middle, int end) {
	int i = begin;
	int j = middle + 1;
	int k = begin;
	//기본적으로 i는 왼쪽 j는 중간 이후부터 시작
	while (i <= middle && j<=end) {
		if (list[i] < list[j]) {
			tempArray[k] = list[i];
			++i;
		}
		else {
			tempArray[k] = list[j];
			++j;
		}
		++k;
	}
	//남은 데이터 삽입 
	//i가 먼저 끝났다.
	if (i >middle) {
		while (j <= end) {
			tempArray[k] = list[j];
			++j;
			++k;
		}
	}
	//j가 끝남
	else {
		while (i <= middle) {
			tempArray[k] = list[i];
			++i;
			++k;
		}
	}
	for (int t = begin; t <= end; ++t)
		list[t] = tempArray[t];
}
void MergeSort(int* list, int begin, int end) {
	if (begin < end) {
		int middle = (begin + end) / 2;
		MergeSort(list, begin, middle);
		MergeSort(list, middle+1, end);
		MergeSort(list, begin, middle, end);
	}
}

int main() {
	int list[10] = { 1,5,4,8,7,6,10,2,9,3 };
	MergeSort(list, 0, MAX_LIST-1);

	std::cout << "Result of Sort:";
	for (auto i : list)
		std::cout << i << " ";
	std::cout << std::endl;
}

 

후기

심화 정렬 알고리즘의 시작인 병합 정렬을 구현해보았다. 퀵 소트나 병합 정렬 모두 분할 정복 알고리즘 인대 이렇게 재귀적으로 알고리즘을 짜는 걸 알 수 있을지 조금 걱정이 된다. 코드 짜는 법은 까먹어도 특징 장단점 구현 방법은 꼭 숙지해야겠다.

 

 

 

 

출처 및 레퍼런스

Wiki: https://ko.wikipedia.org/wiki/합병_정렬

Blog: https://blog.naver.com/ndb796/221227934987