[간단 정리] 합병 정렬

* 오름차순 기준입니다

 

이름에서 알 수 있듯이 합병의 과정에서 데이터가 정렬되는 알고리즘이다. 합병하기 위해선 분할을 해야겠지? 합병 정렬은 분할 정복 알고리즘에 속한다. 연결 리스트로 구현하면 퀵 정렬을 포함한 어느 정렬 알고리즘보다 효율이 좋다고 하지만 배열로 공부했기 때문에 여기에선 배열을 사용한다.

 

최소 단위까지 분할을 하고 나서 합병하면서 대소를 비교해 정렬한다. 분할한다고 해서 매번 그 과정에 배열을 진짜로 나누진 않는다. 인덱스를 가지고 구간을 분할하며, 합병할 때 배열이 등장한다. 주어진 배열에 left, mid, right가 있을 때 분할하는 범위는 left ~ mid와 mid+1 ~ right이다. 나눠서 수행하며 재귀호출로 분할할 수 없을 때까지 분할한다. 즉 마지막까지 분할되면 왼쪽 구간에는 인덱스 하나, 오른쪽 구간에 인덱스 하나가 남는다.

 

위 그림이 마지막 합병 단계라고 해보자. 이번 합병만 끝나면 정렬이 완료된다. 첫 번째 요소부터 비교해가며 새로운 배열에 값을 넣는데, 어느 한 쪽이 먼저 끝난다면 아직 작업되지 않은 구간 전체를 뒤에 이어 복사하면 된다. 다음 그림을 보면 위 그림의 왼쪽 배열이 새로운 배열에 전부 값이 들어갔고 오른쪽 배열은 아직 합병할 부분이 남았다. 이 경우 남은 부분 전체를 이어 복사하면 된다는 이야기다. 지금까지 말한 것이 그대로 소스에 나타난다.

>> 구현

 

#include <cstdio>
#define SIZE 8
int sortedArr[SIZE];
void Merge(int arr[], int left, int mid, int right)
{
	int leftIndex, rightIndex, i;
	leftIndex = left;
	rightIndex = mid + 1;
	i = left; // 새롭게 정렬될 배열의 인덱스

	// 분할 정렬된 배열을 합칠 때 대소를 비교
	while (leftIndex <= mid && rightIndex <= right)
	{
		if (arr[leftIndex] <= arr[rightIndex])
			sortedArr[i++] = arr[leftIndex++];
		else
			sortedArr[i++] = arr[rightIndex++];
	}

	// 어느 한 쪽의 값이 먼저 복사되면 작업이 덜 된 쪽은 그대로 복사
	if (rightIndex > right)
	{
		for (int j = leftIndex; j <= mid; j++)
			sortedArr[i++] = arr[j];
	}
	else 
	{
		for (int j = rightIndex; j <= right; j++)
			sortedArr[i++] = arr[j];
	}

	// 정렬된 배열을 원본에 복사
	for (int j = left; j <= right; j++) 
	{
		arr[j] = sortedArr[j];
	}
}

// 합병 정렬
void MergeSort(int arr[], int left, int right) 
{
	int mid;

	if (left < right) 
	{
		// to avoid overflow
		// same as (left + right) / 2
		mid = left + (right - left) / 2; 
		MergeSort(arr, left, mid);			
		MergeSort(arr, mid + 1, right);		
		Merge(arr, left, mid, right);		
	}
}

void PrintArray(int arr[], int size)
{
	for (int i = 0; i < size; i++)
	{
		printf("%d ", arr[i]);
	}
	printf("\n");
}
int main() 
{
	int arr[SIZE] = { 20, 18, 10, 5, 13, 16, 11, 1 };

	// 정렬 전
	PrintArray(arr, SIZE);

	// 합병 정렬
	MergeSort(arr, 0, SIZE - 1);

	// 정렬 후
	printf("--after sort\n");
	PrintArray(arr, SIZE);

	return 0;
}