[알고리즘] 합병정렬 (Merge Sort) 이란? (C++로 구현하기)

합병정렬이란?

퀵정렬 (Quick Sort) 와 함께 대표적으로 사용되는 빠른 정렬 알고리즘입니다.

얼마나 빠르냐구요? 퀵정렬과 동일하게 O(N * log N) 입니다.

 

물론 완전히 동일한 시간이 걸린다는 것은 아닙니다.

퀵정렬은 최악의 경우 (이미 정렬되어있는 경우) 에서는 O(N²) 까지 걸릴 수 있거든요.

 

하지만 합병정렬은 나누고 병합하는 과정에서 O(N * log N)이 거의 보장됩니다.

그러므로, 특정한 경우에서는 퀵정렬 대신 병합정렬을 사용하기도 합니다.

 

 

 

동작 원리

다음과 같은 배열이 있다고 가정해볼게요.

우리는 병합정렬을 하기 위해서, 크게는 아래 그림과 같은 과정을 거칠 것입니다.

 

그림에서 보시는 것처럼, 합병정렬은 크게 3가지의 과정을 가집니다.

 

(1) 분할

- N 길이의의 배열을 N / 2 길이의 배열 2개로 분할시켜 나갑니다.

(2) 정복

- 부분 배열을 정렬합니다. 부분 배열의 크기가 충분히 작아질 때까지 재귀 호출을 반복합니다.

(3) 결합

- 정렬된 부분 배열을 결합하여, 완성된 배열을 만들어냅니다.

 

분할하는 과정은 단순히 N / 2 길이의 배열 2개로 만드는 것이므로

이해하는데에 어려움이 없으실 것입니다.

정복 및 결합 과정이 어떻게 진행되는지만 이해하시면 합병정렬을 이해할 수 있습니다.

 

위의 왼쪽의 배열과, 오른쪽의 배열은 각각 정렬된 부분배열 입니다.

합쳐지는 과정에서 각각의 값들을 비교한 후에,

새롭게 만들어지는 배열에 오름차순으로 정렬되는 것을 확인하실 수 있습니다.

 

합병정렬은 모든 부분배열에 대해서 위와 같은 과정을 거치고,

최종적으로 완성된 배열을 가지게 됩니다.

 

 

 

구현 (C++)

#include <iostream>
#include <ctime>

#define MAX_ARR 20

using namespace std;

void merge(int *arr, int first, int mid, int last)
{
	int* sorted = new int[last - first + 1];
	int i, j, k;
	i = first;		// First arr idx
	j = mid + 1;	// Second arr idx
	k = 0;			// Sorted arr idx

	while (i <= mid && j <= last)
	{
		if (arr[i] <= arr[j]) sorted[k++] = arr[i++];
		else sorted[k++] = arr[j++];
	}

	if (i > mid) 
		while (j <= last) sorted[k++] = arr[j++];
	else
		while (i <= mid) sorted[k++] = arr[i++];

	for (i = first, k = 0; i <= last; i++, k++) arr[i] = sorted[k];

	delete[] sorted;
}

void mergeSort(int *arr, int first, int last)
{
	if (first < last)
	{
		int mid = (first + last) / 2;
		mergeSort(arr, first, mid);
		mergeSort(arr, mid + 1, last);
		merge(arr, first, mid, last);
	}
}

void print(int* arr, int N, const char* str)
{
	cout << str << '\n';
	for (int i = 0; i < N; i++) cout << arr[i] << " ";
	cout << "\n\n";
}

int main(void)
{
	srand(time(NULL));

	int arr[MAX_ARR];

	for (int i = 0; i < MAX_ARR; i++)
		arr[i] = (rand() % 1000) + 1;

	print(arr, MAX_ARR, "[PREV]");
	mergeSort(arr, 0, MAX_ARR - 1);
	print(arr, MAX_ARR, "[NEXT]");

	return 0;
}