[C++] 머지 정렬 (Merge Sort)

원리

머지 정렬(Merge Search)의 정렬 원리는 다음과 같다.

 

 

머지 정렬은 퀵 정렬과 마찬가지로 Divide and Conquer 방식을 사용한다.

따라서 재귀 함수를 사용하며, 종료 구문이 필요하다.

시간 복잡도는 O(n * Log n)에 해당한다.

 

새로운 메모리를 할당해야 한다는 단점이 있다.

하지만 Instructions 처리 과정에서 원본 메모리 값은 유지된다는 점에서

Stable Sort 기법으로 분류된다.

 

C++ algorithm 헤더 파일의 stable_sort 함수가 머지 정렬을 사용한다.

 

 

 

 

코드

#include <iostream>
#include <vector>

#define VEC_SIZE 10

using namespace std;

/*
아이디어
	1. 배열을 절반으로 나누기 (크기가 1 이하가 되면 멈추기)
	2. 쪼개인 배열들을 투포인터로 비교하며 병합
*/

vector<int> save_vec(VEC_SIZE, 0);

void merge(vector<int>& arr, int l, int mid, int r)
{
	int p1 = l;
	int p2 = mid + 1;
	int k = l; // << 인자 값이 변하면 안되는 부분 처음 알음

	// 정렬하면서 병합
	while (p1 <= mid && p2 <= r)
	{
		if (arr[p1] <= arr[p2])
			save_vec[k++] = arr[p1++];
		else
			save_vec[k++] = arr[p2++];
	}

	// 남은 부분 병합 (남은 부분은 이미 정렬된 상태)
	if (p1 > mid)
	{
		while (p2 <= r)
			save_vec[k++] = arr[p2++];
	}
	else
	{
		while (p1 <= mid)
			save_vec[k++] = arr[p1++];
	}

	// 임시 데이터를 벡터 값에 전달
	for (int i = l; i <= r; i++)
		arr[i] = save_vec[i];
}

void merge_sort(vector<int>& arr, int l, int r)
{
	if (r <= l)
		return;

	int mid = (l + r) / 2;

	// 분할 단계
	merge_sort(arr, l, mid);
	merge_sort(arr, mid + 1, r);

	// 병합 단계
	merge(arr, l, mid, r);
}

int main()
{
	vector<int> arr = { 7, 2, 5, 4, 1, 3, 9, 8, 6, 10 };

	merge_sort(arr, 0, arr.size() - 1);

	for (auto n : arr)
		cout << n << '\n';

	return 0;
}