[알고리즘] 병합 정렬 (Merge Sort)

[알고리즘] 병합 정렬 (Merge Sort)

---

병합정렬은 퀵정렬과 마찬가지로 분할 정복 방법의 알고리즘이며 퀵정렬과 마찬가지로 O(N * logN)의 시간 복잡도를 가진다.

먼저 반을 나누고 나중에 합쳐서 정렬을 하자!!!!

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

7, 10, 5, 8, 1, 6, 3, 4, 2, 9

7 10 5 8 1 | 6 3 4 2 9       //반 나누기

7 10 5 | 8 1 | 6 3 4 | 2 9   //나눈 것을 또 나누기

5 7 10 | 1 8 | 3 4 6 | 2 9   //나눠진 것들 정렬

1 5 7 8 10 | 2 3 4 6 9       //합쳐서 정렬

1 2 3 4 5 6 7 8 9 10

소스코드 구현 (C++)

#include <iostream>
//정렬될 배열을 미리 전역변수로 선언해두자
int Sorted[9999];

void Merge(int* data, int start, int middle, int end)
{
	int i = start;
	int j = middle + 1;
	int index = start;
	//작은 순서대로 배열에 삽입
	while (i <= middle && j <= end)
	{
		//앞에것이 작으면 앞에것을 넣어주기
		if (data[i] <= data[j])
		{
			Sorted[index] = data[i];
			i++;
		}
		//뒤에것이 같거나 크다면 뒤에것을 넣어주기
		else
		{
			Sorted[index] = data[j];
			j++;
		}
		index++;
	}
	//남은 데이터 넣기
	if (i > middle)
	{
		for (int k = j; k <= end; k++)
		{
			Sorted[index] = data[k];
			index++;
		}
	}
	else
	{
		for (int k = i; k <= middle; k++)
		{
			Sorted[index] = data[k];
			index++;
		}
	}
	//정렬된 배열을 삽입
	cout << "[";
	for (int k = start; k <= end; k++)
	{
		data[k] = Sorted[k];
		cout << data[k] << " ";
	}
	cout << "]" << endl;
}

void MergeSort(int* data, int start, int end)
{
	//크기가 1보다 큰 경우
	if (start < end)
	{
		int middle = (start + end) / 2;
		MergeSort(data, start, middle);
		MergeSort(data, middle + 1, end);
		Merge(data, start, middle, end);
	}
}

int main()
{
	int temp;
	int arr[10] = { 1, 10, 5, 8, 7, 6, 3, 4, 2, 9 };
	//병합 정렬
	MergeSort(arr, 0, 9);
	//출력
	for (int i = 0; i < 10; i++)
	{
		cout << arr[i] << ", ";
	}
	return 0;
}

출력 결과

시간 복잡도 계산

일단 데이터를 반으로 나누어서 정렬하기 때문에 logN이며, 또한 나누어진것은 이미 정렬이 되어있는 것이고 이것을  또 정렬하기 때문에 N이다. 즉, 이 두개를 합친 N * logN이 되는 것이다.

---

병합 정렬은 시작점이 아니라 처음부터 반으로 나누면서 시작하기 때문에 O(N * logN)의 시간복잡도를 보장한다. 하지만 기존의 데이터를 담을 추가적인 공간이 필요하며 이것을 전역변수로 선언하여서 사용하였다. 그렇기 때문에 시작복잡도를 보장한다는 장점이 있지만 메모리 활용이 비효율적이라는 문제가 있습니다.