5) 병합정렬

---

병합 정렬은 '분할 정복' 방법을 사용하는 알고리즘이다.
결과적으로 퀵 정렬과 동일하게 O(N*logN)의 시간 복잡도를 가진다.

하지만 퀵정렬과 달리 최악의 경우에도 O(N*logN)를 보장한다는 차이점이 있다.

다음 문제를 살펴보자.

다음의 숫자들을 오름차순으로 정렬하는 프로그램을 작성하세요.

( 7, 6, 5, 8, 3, 5, 9, 1 )

#include <iostream>
using namespace std;

int number = 8;
int sorted[8];

void merge(int a[], int m, int middle, int n){
	int i = m;
	int j = middle + 1;
	int k = m;
	while (i <= middle && j <= n) {
		if (a[i] <= a[j]) {
			sorted[k] = a[i];
			i++;
		}
		else {
			sorted[k] = a[j];
			j++;
		}
		k++;
	}

	if (i > middle) {
		for (int t = j; t <= n; t++)
		{
			sorted[k] = a[t];
			k++;
		}
	}
	else
	{
		for (int t = i; t <= middle; t++)
		{
			sorted[k] = a[t];
			k++;
		}
	}
	for (int t = m; t <= n; t++)
	{
		a[t] = sorted[t];
	}
}

void mergesort(int a[], int m, int n) {
	if (m < n) {
		int middle = (m+n) / 2;
		mergesort(a, m, middle);
		mergesort(a, middle + 1, n);
		merge(a, m, middle, n);
	}
}

int main(void) {
	
	int array[8] = { 7, 6, 5, 8, 3, 5, 9, 1 };
	mergesort(array, 0, number - 1);
	for (int t = 0; t < number; t++)
	{
		cout << array[t];
	}
	
}

---

병합 정렬은 두 개의 작은 문제로 분할한 뒤에 각자 계산하고 나중에 합치는 방법이다.

풀이와 같이 8개의 배열공간이 존재하면 mergesort로 절반씩 나눠간다.

[ 7, 6, 5, 8, 3, 5, 9, 1 ]
위 배열을 절반으로 나뉜다.

[7 ,6, 5, 8]     [3, 5, 9, 1]

또 나뉜다.

[6, 7]  [5, 8]  [3, 5]  [1, 9]

그리고 위 처럼 작고 큰 숫자를 비교해 순서를 바꾼다.

[6, 7]  [5, 8]

그 다음 위 숫자들을 정렬하며 한 단계씩 합쳐 나간다.

[5, 6, 7, 8]

---

병합 정렬을 구현할 때 신경써야 하는 부분은
정렬에 사용되는 배열을 '전역 변수'로 선언해야 한다는 것이다.

함수 안에서 배열을 선언하게 된다면 매 번 배열을 선언해야
한다는 점에서 메모리 자원의 낭비가 매우 커질 수 있기때문이다.

기본적으로 기존의 데이터를 담을 추가적인 배열공간이
필요하다는 점에서 메모리 활용이 비효율적이라는 문제가 있다.

병합 정렬은 퀵 정렬보다 느리지만 O(N*logN)을 보장할 수 있다는 점에서 효율적인 알고리즘이다.