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

01. 병합 정렬의 개념

• 안정 정렬이다. 
• 정렬을 위한 별도의 공간이 필요하다.
• 분할 정복 알고리즘이다.
• 주로 순환 호출로 구현
• 매우 빠른 속도를 보장 ( O(NlogN) )

02. 과정 설명

1. 배열을 반으로 나누는 것을 반복한다.
2. 사이즈 1짜리 배열까지 나누고 나면, 나눈 순서의 역순으로 정렬해가며 부분 배열을 합친다.

말로는 사실 설명할 게 별로 없다...

그림으로 보는 게 더 설명이 쉬울 듯 하여 첨부

03. C++ 코드

void Merge(int*& arr, int*& tmp, int left, int right)
{
	if (left == right)
		return;

	int l = left;
	int mid = (l + right) / 2;
	int midIdx = mid + 1;
	int idx = l;

	// 작은 원소 순서대로 임시 배열에 채워넣는다.
	while (l <= mid && midIdx <= right)
	{
		if (arr[l] < arr[midIdx])
			tmp[idx++] = arr[l++];
		else
			tmp[idx++] = arr[midIdx++];
	}

	// 남아있는 원소들을 임시 배열에 넣는다. 
	while (l <= mid)
		tmp[idx++] = arr[l++];
	while (midIdx <= right)
		tmp[idx++] = arr[midIdx++];

	// 원래 배열에 정렬된 임시 배열을 복사 
	for (int i = left; i <= right; ++i)
		arr[i] = tmp[i];
}

void MergePartitioning(int*& arr, int*& tmp, int left, int right)
{
	if (left >= right)
		return;

	int mid = (left + right) / 2;

	// 분할부터 수행한다
	MergePartitioning(arr, tmp, left, mid);
	MergePartitioning(arr, tmp, mid + 1, right);

	// 부분 배열을 합병 정렬한다.
	Merge(arr, tmp, left, right);
}

void MergeSort()
{
	cout << "Merge Sort : " << endl;

	int* arr = new int[6]{ 5, 1, 8, 9, 7, 3 };
	int* tmp = new int[6]{ 0, 0, 0, 0, 0, 0 };

	MergePartitioning(arr, tmp, 0, 5);

	for (int i = 0; i < 6; ++i)
		cout << arr[i] << " ";
	cout << '\n';

	delete[] arr;
	delete[] tmp;
}

05. 병합 정렬의 시간 복잡도

• 레코드의 크기 N = 2^k 인 경우, 순환 호출의 깊이는 pivot에 의해 균등하게 나누어진다고 가정할 때 log2^k = k이다.
• size 1 짜리 부분 배열은 비교를 위해 1번의 연산을 수행
• size 2 짜리 부분 배열은 비교를 위해 2번의 연산을 수행
• size 4 짜리 부분 배열은 비교를 위해 4번의 연산을 수행
• 2^k-1 짜리 부분 배열은 비교를 2^k-1 번 하게 되고, 이 부분 배열은 2개가 있다.
  • 따라서 비교 연산은 2^k-1 * 2 = 2^k 번
• 즉, 각 순환 호출마다 N번의 연산을 수행하게 된다.
• 따라서 전체 시간 복잡도는 O(NlogN)