[Algorithm] 정렬 - 합병 정렬 (Merge Sort)

합병 정렬(Merge Sort)이란?

- 작은 조각까지 나눠, 조각을 병합하면서 정렬하는 방식이다.

- 일반적인 방법으로 구현했을 때 이 정렬은 안정 정렬에 속한다.

- 분할 정복 알고리즘의 하나이다.

 

 

작동 방식

1) 리스트를 절반으로 계속해서 나눈다. (분할)

2) 가장 작은 단위로 나눠지면, 나눠진 두 조각의 값들을 비교한다.

3) 두 리스트를 비교하면서 하나의 정렬된 리스트에 값을 정렬한다. (합병)

 

 

소스코드

#include <iostream>

using namespace std;

int* sorted;

void mergeSort(int* arr, int left, int right);
void merge(int* arr, int left, int right);

int main() {
	int N;
	cin >> N;
	
	sorted = new int[N];

	int* arr = new int[N];
	for (int i = 0; i < N; i++) {
		cin >> arr[i];
	}

	mergeSort(arr, 0, N - 1);

	for (int i = 0; i < N; i++) {
		cout << arr[i] << endl;
	}

	delete[] arr;
	delete[] sorted;

	return 0;
}

void mergeSort(int* arr, int left, int right) {
	int mid;
	if (left < right) {
		mid = (left + right) / 2;
        
        // 분할
		mergeSort(arr, left, mid);
		mergeSort(arr, mid + 1, right);
        
        // 합병
		merge(arr, left, right);
	}
}

void merge(int* arr, int left, int right) {
	int mid = (left + right) / 2;
	int l = left;
	int r = mid + 1;

	int i = left;
	while (l <= mid && r <= right) {
		if (arr[l] < arr[r]) {
			sorted[i++] = arr[l++];
		}
		else {
			sorted[i++] = arr[r++];
		}
	}

	// 남은 수들
	if (l <= mid) {
		for (l; l <= mid; l++) {
			sorted[i++] = arr[l];
		}
	}
	else {
		for (r; r <= right; r++) {
			sorted[i++] = arr[r];
		}
	}
	
    // arr배열에 값 복사
	for (int j = left; j <= right; j++) {
		arr[j] = sorted[j];
	}
}

 

 

소스코드 이해

합병정렬은 보통 재귀로 구현한다.

합병정렬이라고 검색하면 흔히 나오는 그림들을 보며 작동 방식을 이해하는 데는 큰 어려움이 없었다.

하지만 막상 구현하려고 하니 어떻게 작성해야 할 지 막막해 흐름을 그림으로 그려보았다.

 

아래는 소스코드 진행 흐름 그대로 작동 방식을 표현한 그림이다. (일부)

① ~ ④ 배열의 왼쪽부분 부터 길이가 1일 때까지(left == right) 쪼갠다.

⑤ 배열의 왼쪽, 오른쪽 부분 값을 비교하여, 작은 값부터 sorted 배열에 저장한다.

   정렬된 부분을 다시 비교해야 하므로, 정렬된 부분을 arr배열에 copy한다.

⑦ ①에서 나눈 왼쪽부분을 분할 및 정렬했으므로, 오른쪽 부분을 분할한다.

⑧ 배열의 왼쪽, 오른쪽 부분 값을 비교하여, 작은 값부터 sorted 배열에 저장한다.

   정렬된 부분을 다시 비교해야 하므로, 정렬된 부분을 arr배열에 copy한다.

 

 

시간복잡도

평균의 경우 : O(nlogn)

최선의 경우 : O(nlogn)

최악의 경우 : O(nlogn)

 

배열을 길이가 1일 때 까지 계속 절반으로 쪼개면, 그 깊이는 logn이 된다.

나눌 수록 배열의 개수는 많아지지만, 데이터는 n개로 모두 동일하다.

따라서 각 깊이별로 수행되는 연산의 시간복잡도는 O(n)이다.

 

이를 종합하면 시간복잡도는 O(nlogn)이 된다.