[Algorithm] C++ Merge Sort (병합정렬)

병합정렬

• List를 반으로 더이상 나눌 수 없을때까지 반으로 나누고(Divide - 분할),
• 나누어진 부분 List들을 두개씩 짝지어 정렬(Conquer - 정복)하며 합치는(Combine - 결합)과정을 반복하는 방법

 

병합정렬 알고리즘

• 하나의 List를 더 이상 나눠질 수 없을 때 까지 반으로 분할한다.
• 더 이상 나눌 수 있는 List가 없을 경우, 반복적으로 나뉘어진 부분 List들을 정렬하며 합친다.

 

예시

출처 - https://runestone.academy/ns/books/published/pythonds/SortSearch/TheMergeSort.html

병합정렬의 알고리즘은 기본적으로 분할정복을 사용한다.

원소들의 List를 계속하여 나뉘어지지 않을때 까지 반으로 나누는 재귀 알고리즘을 이용한다.

원소 List에 둘 이상의 원소가 있는 경우 List를 분할하고, 양쪽 절반에 대해 병합정렬을 재귀적으로 호출하여 진행한다.

아래의 그림은 분할한 원소들을 다시 병합하는 과정을 보여준다.

출처 - https://runestone.academy/ns/books/published/pythonds/SortSearch/TheMergeSort.html

위의 그림은 두 개의 정렬된 List들을 가져와 하나의 정렬된 새 List로 결합하는 과정이다.

분할된 원소들을 비교하여 작은 원소가 앞으로 오도록 정렬하며 병합하는 과정을 나타낸다.

 

아래 그림은 병합정렬의 프로세스를 쉽게 나타낸다.

출처 - https://ko.wikipedia.org/wiki/%ED%95%A9%EB%B3%91_%EC%A0%95%EB%A0%AC

 

병합정렬 특징

• 주어진 배열 이외에 다른 추가 메모리를 요구한다. (추가적인 List가 필요하다)
• 중복된 값은 입력 순서와 동일하게 정렬되는 안정 정렬(Stable Sort)이다.
• 데이터들 간의 상대적 크기 관계만을 이용해서 정렬하는 비교 정렬이다.
• 분할 정복 알고리즘을 기반으로 정렬되는 방식으로, 퀵 정렬과는 다르게 항상 균등하게 List가 나뉜다.
• 일반적으로 퀵 정렬 보다 느리다.

 

시간복잡도

• 병합 정렬의 시간복잡도는 O(NlogN)의 시간복잡도를 갖는다.
• Best : O(NlogN)
• Avg  : O(NlogN)
• Worst : O(NlogN)

 

관련 알고리즘 문제

https://www.acmicpc.net/problem/23297

23297번: 전파와 병합 1

https://www.acmicpc.net/problem/24062

24062번: 알고리즘 수업 - 병합 정렬 3

 

Code

#include <iostream>

using namespace std;

// 분할하는 리스트를 따로 설정하지않고 하나만 설정
int sorted[8];

// 합병 함수
void merge(int arr[], int start, int end) {
	int mid = (start + end) / 2;
	int i = start;
	int j = mid + 1;
	int k = start;

	//왼쪽 리스트와 오른쪽 리스트의 값을 비교(정렬)하면서 sorted란 배열에 합친다.
	while (i <= mid && j <= end) {
		if (arr[i] < arr[j]) {
			sorted[k++] = arr[i++];
		}
		else {
			sorted[k++] = arr[j++];
		}
	}
	if (i > mid) {
		while (j <= end) {
			sorted[k++] = arr[j++];
		}
	}
	if (j > end) {
		while (i <= mid) {
			sorted[k++] = arr[i++];
		}
	}


	for (int i = 0; i <= end; i++) {
		arr[i] = sorted[i];
		cout << arr[i] << ' ';
	}
	cout << '\n';

}

//주어진 정렬을 더 이상 나눌 수 없을 때 까지 쪼갠 후, 크기가 1인 배열들을 순차적으로 합치며 정렬한다.
void mergeSort(int arr[], int start, int end) {

	if (start < end) {
		int mid = (start + end) / 2;
		mergeSort(arr, start, mid);
		mergeSort(arr, mid + 1, end);
		merge(arr, start, end);
	}

}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int arr[9] = { 54, 26, 93, 17, 77, 31, 44, 55, 20 };

	mergeSort(arr, 0, 7);

}