[자료구조] 합병 정렬 (merge sort)

합병 정렬이란?

합병 정렬은 리스트를 분할하고 결합하는 과정 속에서 정렬을 수행하고자 하는 방법입니다. 분할-정복에 따른 수행 방식입니다.

앞서 정렬을 할 때는 기존의 리스트를 그대로 이용해서 수행했습니다. 숫자가 적을 때는 시간이 오래 걸리지 않지만, 커지면 시간 복잡도에 따라 수행 시간이 어마하게 늘어남을 알 수 있습니다.

 

합병 정렬은 기존의 리스트를 쪼개서 더 작은 리스트를 만듭니다(분할). 쪼갤 수 있을 때까지 쪼갭니다(정복) 문제를 충분히 작게 만들었다면, 정렬을 합니다. 이 때 정렬은 숫자 단 두개만을 비교합니다.

정렬을 했다면, 다시 원래 리스트의 크기로 돌아갈 있도록 합쳐줍니다(결합). 합쳐주는 과정에서도 순서대로 숫자가 들어가야 합니다. 따라서 분리되어 있는 리스트의 맨 앞에서 하나씩 꺼내 비교해주면서 넣어줍니다.

 

합병 정렬 구현

합병 정렬의 핵심은 분할-정복-결합입니다.

 

과정은 아래와 같습니다.

1. 하나의 리스트를 두 리스트로 분할
   • 단, 각각의 리스트를 분할할 수 있다면 1.을 다시 수행
2. 분할된 부분 리스트 정렬
3. 정렬된 리스트 결합
   • 단, 각각의 리스트를 결합할 수 있다면 3.을 다시 수행

 

코드로 구현하면 아래와 같습니다.

void merge(int list[], lit left, int mid, int right) {
	int i = left, j = mid + 1, k = left, l;

	while(i <= mid && j <= right) {
		if(list[i] <= list[j]) {
			sorted[k++] = list[i++];
		} else {
			sorted[k++] = list[j++];
		}
	}
	if(i > mid) {
		for(l = j; l <= right; l++) {
			sorted[k++] = list[l];
		}
	} else {
		for(l = i; l <= mid; l++) {
			sorted[k++] = list[l];
		}
	}
    
	for(l = left; l <= right; l++) {
		list[l] = sorted[l];
	}
}

void merge_sort(int list[], int left, int right) {
	int mid;
	if(left < right) {
		mid = (left + right) / 2;
		merge_sort(list, left, mid);
		merge_sort(list, mid + 1, right);
		merge(list, left, mid, right);
	}
}

 

합병 정렬의 시간 복잡도

합병 정렬은 최악, 최선, 평균 모두 $O(n \space log \space n)$에 수행됩니다.

 

 

[자료구조] 선택 정렬 (selection sort)

[자료구조] 삽입 정렬 (insertion sort)

[자료구조] 버블 정렬 (bubble sort)

[자료구조] 셸 정렬 (shell sort)

[자료구조] 퀵 정렬 (quick sort)

[자료구조] 힙 정렬 (heap sort)

[자료구조] 기수 정렬 (radix sort)