[Algorithm] 병합 정렬(Merge Sort)

병합 정렬이란?

일단 반으로 쪼개고 나중에 합치는 정렬이다.
퀵 정렬과 다른 점은 항상 반으로만 나누기에 피벗값이 따로 필요없다는 점이다.
합병 정렬은 다음 단계들로 이루어진다.

• 분할(Divide) : 입력 배열을 같은 크기의 2개의 부분 배열로 분할한다.
• 정복(Conquer) : 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 순환 호출을 이용하여 다시 분할 정복 방법을 적용한다.
• 결합(Combine) : 정렬된 부분 배열들을 하나의 배열에 합병한다.

예시를 들어 살펴보겠습니다.

7 6 5 8 3 5 9 1

1. left가 먼저 실행됩니다. 7 6 5 8 -> 7 6 -> 7
2. left가 다 끝났다면 right를 실행시켜줍니다. 6
3. right가 끝났으니 merge함수를 실행해줍니다. 7과 6을 비교하여 6 7로 정렬해줍니다.
4. 위 과정을 정렬될 때까지 반복합니다.

전체적인 실행순서는 다음과 같습니다.

7 6 5 8 -> 7 6 -> 7 -> 6 -> merge(6, 7)
-> 5 8 -> 5 -> 8 -> merge(5, 8) -> merge(5, 6, 7, 8)

3 5 9 1 -> 3 5 -> 3 -> 5 -> merge(3, 5) -> 9 1 -> 9 -> 1 -> merge(1, 9) -> merge(1, 3, 5, 9)

-> merge(1, 3, 5, 5, 6, 7, 8, 9) -> 1 3 5 5 6 7 8 9

코드

#include<iostream>

using namespace std;

int N,arr[1000001];
int *arr2;

void merge(int left, int right)
{
	int mid = (left + right) / 2;

	int i = left;
	int j = mid + 1;
	int k = left;
	while (i <= mid && j <= right)
	{
		if (arr[i] <= arr[j]) 
			arr2[k++] = arr[i++]; 
		else
			arr2[k++] = arr[j++];
	}

	int tmp = i>mid ? j : i;
	
	while(k<=right) arr2[k++] = arr[tmp++];

	for (int i=left;i<=right;i++) arr[i] = arr2[i];
}

void partition(int left,int right)
{
	int mid;
	if (left < right)
	{
		mid = (left + right) / 2; 
		partition(left, mid);
		partition(mid + 1, right);
		merge(left, right);
	}
}

int main()
{
	scanf("%d",&N);
	arr2 = new int[N];
	for (int i=0;i<N;i++) scanf("%d",&arr[i]);

	partition(0, N - 1);

	for (int i=0;i<N;i++) printf("%d\n",arr[i]) ;
}

시간 복잡도

가로 배열의 개수가 n개이고, 깊이가 $log_2n$과 같기에 둘을 곱해주면 $n * log_2n$ 과 같다.

$O(nlog_2n)$

참고

블로그