[Algorithm] 병합 정렬(Merge Sort) 코드와 시간 복잡도

인트로

합병 정렬 또는 병합 정렬은 $O(NlogN)$ 시간 복잡도를 갖는 정렬 알고리즘으로 분할 정복 패러다임에 기반한다.

 

추가로 삽입 정렬, 버블 정렬, 선택 정렬이 추가적인 자료구조 없이 정렬하는 Inplace 정렬이라면 

병합 정렬은 정렬한 데이터를 추가적인 임시 공간에 저장한다.

병합 정렬(Merge Sort) : 개념

https://jinhyy.tistory .com/9

앞서 언급했듯 병합 정렬은 분할 정복 패러다임에 기반한 알고리즘으로 큰 문제를 아주 작은 문제로 나눈 뒤 작은 문제를 해결하며 최종적으로 큰 문제를 해결한다.  

 

다음과 같은 데이터가 배열에 저장되어 있다.

 

분할 : 본 배열을 더 이상 쪼갤 수 없을 때까지 쪼개면 [3] [44] [38] [5] [47] [15] [36] [26] 다음과 같은 형태가 된다.

정복 : 두 집합을 하나로 합쳐 정렬을 한다. 즉 [3]과 [44]을 합치고 정렬 [38]과 [5], [47]과 [15], [36]과 [26]을 각각 합치고 정렬하면 다음과 같다. [3, 44] [5, 38] [15, 47], [26, 36] 

 

이처럼 병합 정렬은 큰 문제를 작은 문제로 분할하고 큰 문제가 될 때까지 정복(정렬) 과정을 거쳐 해를 찾는다.

 

여기까지 이해했다면 자연스럽게 한 가지 사실을 알 수 있는데 병합하는 과정은 총 세 단계로 단계의 높이는 $logN$을 따른 다는것이다.

 

이해하기 조금 어렵다면 본 예제를 보면 쉬운데, 가장 작게 분할한 배열의 길이는 항상 1이며 병합하는 과정에서 2배씩 커진다. 결국 $2^x = 8$을 만족하는 $x$를 찾아야 하는데 양변에 밑이 2인 $log$를 취하면 $x = 3$으로 단계의 높이는 3이 된다. 

일반화해서 길이가 $N$인 임의의 배열에 대해서 높이를 구하면 $2^x = N$을 만족하는 $x$을 찾아야 한다. 앞선 과정과 동일하게 양변에 2인 $log$를 취해 높이$x$을 구하면 다음과 같은 식이 나온다. $x = logN$ 

 

즉 단계의 높이 $x$는 배열의 길이 $N$에 의해 결정된다.

 

 

나아가 각 단계에서 정렬에 필요한 총 반복 횟수는 $N$이기에 전체 시간 복잡도는 높이 * 반복 횟수인  $O(NlogN)$이다.

 

여기서 한 가지 의문이 들 수 있는데 왜 정렬에 필요한 반복 횟수는 $N$일까?

 

위 그림에서 초록색 부분을 보자. 여기 [3, 44] [5, 38] 두 배열의 시작 위치를 가리키는 변수 p1과 p2가 있으며 임시 공간의 시작 위치를 가리키는 p3도 있다. 이제 두 배열을 합쳐 임시 공간에 정렬된 상태로 저장할 계획이다.

 

 

p1과 p2가 가리키는 값의 크기를 비교하고 더 작은 값 3을 임시 공간에 넣고 더 작은 값을 가리키는 인덱싱 변수 p1을 1 증가시킨다.

 

 

한 번 더 수행해 보면 44와 5를 비교하고 더 작은 값 5를 임시 공간에 넣고 p2의 값과 p3의 값을 증가시킨다.

이러한 반복 과정을 거치면 $N$번의 비교만에 두 배열을 정렬된 하나의 배열로 만들 수 있다.

 

따라서 병합 정렬의 시간 복잡도가 $O(NlogN)$임을 다시 한 번 확인할 수 있다. 

병합 정렬(Merge Sort) : 코드

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int n, p1, p2, p3;
int arr[101];
int tmp[101];

void divide(int lt, int rt)
{
	if(lt < rt)
	{
		int mid = (lt + rt) / 2;

		divide(lt, mid);
		divide(mid + 1, rt);

		p1 = lt;
		p2 = mid + 1;
		p3 = lt;

		while (p1 <= mid && p2 <= rt)
		{
			if (arr[p1] < arr[p2])
				tmp[p3++] = arr[p1++];
			else
				tmp[p3++] = arr[p2++];
		}

		while (p1 <= mid)
			tmp[p3++] = arr[p1++];
		while (p2 <= rt)
			tmp[p3++] = arr[p2++];

		for (int i = lt; i <= rt; i++)
			arr[i] = tmp[i];;
	}
}

int main()
{
	cin >> n;

	for (int i = 1; i <= n; i++)
		cin >> arr[i];

	divide(1, n);

	for (int i = 1; i <= n; i++)
		cout << arr[i] << " ";
}

시간 복잡도

병합 단계의 높이 $logN$

각 단계에서 정렬에 필요한 반복 횟수는 $N$

 

따라서 시간 복잡도는 높이 * 반복 횟수인  $O(NlogN)$이다.

https://gmlwjd9405.github.io/2018/05/08/algorithm-merge-sort.html