병합(합병) 정렬(Merge Sort)

 병합정렬(Merge-sort)은 퀵 정렬(Quick Sort)와 같이 분할정복 알고리즘을 이용한 정렬 알고리즘중 하나입니다. 선택정렬같은 O(N²)의 느린 정렬 알고리즘과 다르게 병합정렬은 시간복잡도 O(NlogN)의 빠른 정렬 알고리즘입니다.

---

「병합 정렬의 동작 과정」

---

1. 분할 과정 (Divide)

 병합정렬의 첫 번째 단계인 분할과정에서는 배열을 가능한 한 작게 나눕니다. 이 단계에서는 배열을 중간을 기준으로 두 개의 하위 배열로 분할합니다. 이 과정을 배열에 원소가 하나가 될때까지 계속 반복하면 됩니다.

 

-처음 주어진 배열 ↓

[38, 27, 43, 3, 9, 82, 10]

-첫번째 분할 ↓

[38, 27, 43], [3, 9, 82, 10]

-두번째 분할 

[38, 27], [43],  [3, 9], [82, 10]

-세번째 분할

[38], [27], [3], [9], [82], [10]

---

2. 정복 과정 (Conquer)

 정복(Conquer) 단계에서는 위 과정에서 나누어진 배열들중 서로 인접한 배열을 비교하며 병합합니다. 배열의 크기가 1이 될 때까지 분할한 배열들을 두 개씩 비교하여 정렬된 배열로 병합합니다. 이 과정을 반복하여 더 큰 정렬된 배열을 만듭니다.

-첫번째 과정

[38]과 [27]을 비교하여 [27, 38]으로 병합

-두번째 과정

[3]과 [9]을 비교하여 [3, 9]으로 병합

-세번째 과정

[82]과 [10]을 비교하여 [10, 82]으로 병합

---

3. 결합 과정 (Combine)

 마지막 결합 단계는 정렬된 하위 배열들을 다시 병합하여 최종적으로 전체 배열을 정렬된 상태로 만드는 과정입니다.

-첫번째 과정

[27, 38]과 [43]을 병합하여 [27, 38, 43]으로 병합

-두번째 과정

[3, 9]과 [10, 82]을 병합하여 [3, 9, 10, 82]으로 병합

-마지막 과정

[27, 38, 43]과 [3, 9, 10, 82]을 병합하여 최종 정렬된 배열 [3, 9, 10, 27, 38, 43, 82]이 만들어짐.

하지만 이렇게만 보면 결합과정에 대해 이해가 안가기 때문에 마지막 과정을 통해 결합과정(Combine 또는 Merge)에 대해 자세히 설명해보겠습니다.

 

배열 a

27

38

43

배열 b

3

9

10

82

 

위 두 배열을 Merge하는 과정은 다음과 같습니다.

27

38

43

↑ i

3

9

10

82

↑ j

 

i의 값과 j의 값을 비교하여 더 작은 값을 정답 배열에 넣어줍니다. 

 

-현재 정답배열 = [3]

 

넣었다면 더 작은 배열의 idx값인 j를 증가시킵니다.

27

38

43

↑ i

3

9

10

82

↑ j

 

그후 i의 값과 j의 값을 비교하여 더 작은 값을 정답 배열에 넣어줍니다. 

 

-현재 정답배열 = [3, 9]

 

넣었다면 더 작은 배열의 idx값인 j를 증가시킵니다.

27

38

43

↑ i

3

9

10

82

↑ j

 

그후 i의 값과 j의 값을 비교하여 더 작은 값을 정답 배열에 넣어줍니다. 

 

-현재 정답배열 = [3, 9, 10]

 

넣었다면 더 작은 배열의 idx값인 j를 증가시킵니다.

27

38

43

↑ i

3

9

10

82

↑ j

 

그후 i의 값과 j의 값을 비교하여 더 작은 값을 정답 배열에 넣어줍니다. 

 

-현재 정답배열 = [3, 9, 10, 27]

 

넣었다면 더 작은 배열의 idx값인 i를 증가시킵니다.

27

38

43

↑ i

3

9

10

82

↑ j

 

그후 i의 값과 j의 값을 비교하여 더 작은 값을 정답 배열에 넣어줍니다. 

 

-현재 정답배열 = [3, 9, 10, 27, 38]

 

넣었다면 더 작은 배열의 idx값인 i를 증가시킵니다.

27

38

43

↑ i

3

9

10

82

↑ j

 

그후 i의 값과 j의 값을 비교하여 더 작은 값을 정답 배열에 넣어줍니다. 

 

-현재 정답배열 = [3, 9, 10, 27, 38, 43]

 

넣었다면 더 작은 배열의 idx값인 i를 증가시켜야 하지만 a배열은 이미 끝났음으로 남은 b배열을 모두 정답에 넣어줍니다.

 

-현재 정답배열 = [3, 9, 10, 27, 38, 43, 82]

 

이 과정을 모든 결합과정에서 해준다면 배열이 모두 정렬됩니다.

---

병합정렬을 공부했으니 다음 문제를 병합정렬을 통해 풀어보자

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

《소스코드》

#include <stdio.h>

int n;
int arr[1000010];
int res[1000010];

void Merge(int low, int mid, int high) {
	int i;
	
	int res_len = 0;
	int pointer_first = low;
	int pointer_second = mid + 1;

	while (pointer_first <= mid && pointer_second <= high) {
		if (arr[pointer_first] < arr[pointer_second]) {
			res[res_len++] = arr[pointer_first++];
		}
		else {
			res[res_len++] = arr[pointer_second++];
		}
	}
	if (pointer_first > mid) {
		for (i = pointer_second; i <= high; i++) {
			res[res_len++] = arr[i];
		}
	}
	else if (pointer_second > high) {
		for (i = pointer_first; i <= mid; i++) {
			res[res_len++] = arr[i];
		}
	}
	for (i = low; i <= high; i++) {
		arr[i] = res[i - low];
	}
	return;
}

void Merge_sort(int low, int high) {
	int mid = (low + high) / 2;
	if (low >= high) return;
	Merge_sort(low, mid);
	Merge_sort(mid + 1, high);
	Merge(low, mid, high);
}

int main()
{
	int i;
	scanf("%d", &n);
	for (i = 0; i < n; i++) scanf("%d", &arr[i]);
	Merge_sort(0, n - 1);
	for (i = 0; i < n; i++) printf("%d\n", arr[i]);
	return 0;
}