[Sorting] Merge Sort(병합 정렬)

 정렬(Sorting)은 항목들을 특정한 순서(예: 오름차순, 내림차순)에 따라 배열하는 것을 말한다. 데이터를 정렬하여 보관하면, 데이터의 검색(Searching)이 용이해 문제의 복잡도를 크게 감소시킬 수 있다.

 

 데이터를 정렬하는 방법에는 여러 가지가 있는데, 병합 정렬(Merge Sort)는 분할 정복(Divide-and_Conquer)의 방식으로 데이터를 정렬하며 O(N log N)의 시간 복잡도로 수행된다. 우선 배열의 처음 인덱스와 끝 인덱스의 절반을 기준으로 배열의 왼쪽 영역과 오른쪽 영역을 나누어준다. 이렇게 배열의 크기를 계속해서 분할하여 각각의 크기가 1이 되었을 때, 합치는 작업을 수행하며 정렬을 진행한다.

 

데이터를 분할하는 과정은 다음과 같이 재귀적으로 이루어진다.

// C/C++로 작성된 코드

void MergeSort(int Arr[], int temp[], int left, int right_end) {
	if (left < right_end) { // 데이터의 개수가 2개 이상인 경우 배열을 왼쪽 영역과 오른쪽 영역으로 분할
		int mid = (left + right_end) / 2;
		MergeSort(Arr, temp, left, mid); // 왼쪽 영역에 대하여 재귀적으로 진행
		MergeSort(Arr, temp, mid + 1, right_end); // 오른쪽 영역에 대하여 재귀적으로 진행
		Merge(Arr, temp, left, mid + 1, right_end); // 데이터를 합치면서 정렬하는 작업
		return;
	}
	else // 데이터의 개수가 1개인 경우
		return;	
}

 데이터를 분할하는 함수인 MergeSort는 4개의 인자를 갖는다.
- 첫 번째 인자로는 정렬하고 싶은 배열 A가 들어온다.

- 두 번째 인자로는 정렬하고 싶은 배열과 크기가 같은 배열 B가 들어온다. 그 이유는 분할되어 있는 데이터를 합치는 과정에서 임시적으로 데이터를 저장하는 공간이 필요하기 때문이다. 

- 세 번째 인자로는 정렬하고 싶은 구간의 시작 인덱스 left가 들어온다.

- 네 번째 인자로는 정렬하고 싶은 구간의 마지막 인덱스 right가 들어온다.

 데이터를 모두 분할하였다면, 데이터를 합치는 작업과 동시에 정렬을 진행한다. 왼쪽 배열과 오른쪽 배열을 합치는 과정에서 투 포인터 알고리즘을 사용하여 미리 확보해 놓은 임시 공간 배열 B에 정렬된 배열을 저장한다. 만약, 오름차순으로 데이터를 정렬하고자 한다면 포인터 두 개의 초기값을 각각 왼쪽 배열의 시작 인덱스와 오른쪽 배열의 시작 인덱스로 설정하고, 둘을 비교하여 작은 값을 임시 배열에 저장한다. 그 뒤, 값이 선택된 쪽의 배열의 포인터를 한 칸 이동한다. 

void Merge(int Arr[], int temp[], int left, int right, int right_end) {
	int i, j, pos; // 왼쪽 배열의 포인터 i, 오른쪽 배열의 포인터 j, 임시 배열의 포인터 pos
	i = left; // 왼쪽 배열의 시작 인덱스는 left
	j = right; // 오른쪽 배열의 시작 인덱스는 right(mid +1)
	pos = left; // 임시 배열의 시작 인덱스는 left, left ~ right_end 범위의 정렬을 진행할 것이므로
	while (i <= right - 1 && j <= right_end) { // 포인터가 왼쪽 배열의 끝, 혹은 오른쪽 배열의 끝에 다다를 때 까지 진행
		if (Arr[i] < Arr[j]) { // 오름차순으로 정렬
			temp[pos] = Arr[i];
			i++; // 왼쪽 포인터 한 칸 이동
			pos++; // 임시 배열이 한 칸 채워짐
		}
		else {
			temp[pos] = Arr[j];
			j++; // 오른쪽 포인터 한 칸 이동
			pos++; // 임시 배열이 한 칸 채워짐
		}
	}
	while (i <= right - 1) { // 오른쪽 배열이 먼저 전부 채워진 경우, 남은 왼쪽 배열의 모든 데이터는 오른쪽 배열보다 크다
		temp[pos] = Arr[i];
		i++; // 왼쪽 포인터 한 칸 이동
		pos++; // 임시 배열이 한 칸 채워짐
	}
	while (j <= right_end) { // 왼쪽 배열이 전부 채워진 경우, 남은 오른쪽 배열의 모든 데이터는 왼쪽 배열보다 크다
		temp[pos] = Arr[j];
		j++; // 오른쪽 포인터 한 칸 이동
		pos++; // 임시 배열이 한 칸 채워짐
	}
	for (i = left; i <= right_end; i++)
		Arr[i] = temp[i]; // 임시 배열에 정렬된 데이터를 원래 배열에 저장
	return;
}

전체 과정은 다음과 같다.

void MergeSort(int Arr[], int temp[], int left, int right_end);
void Merge(int Arr[], int temp[], int left, int right, int right_end);

void MergeSort(int Arr[], int temp[], int left, int right_end) {
	if (left < right_end) {
		int mid = (left + right_end) / 2;
		MergeSort(Arr, temp, left, mid);
		MergeSort(Arr, temp, mid + 1, right_end);
		Merge(Arr, temp, left, mid + 1, right_end); // 오른쪽 배열의 첫 인덱스는 mid+1
	}
}

void Merge(int Arr[], int temp[], int left, int right, int right_end) {
	int i, j, pos;
	i = left;
	j = right;
	pos = left;
	while (i <= right - 1 && j <= right_end) { // 왼쪽 배열의 마지막 인덱스는 오른쪽 배열의 첫 인덱스 - 1
		if (Arr[i] < Arr[j])
			temp[pos++] = Arr[i++];
		else
			temp[pos++] = Arr[j++];		
	}
	while (i <= right - 1)
		temp[pos++] = Arr[i++];
	while (j <= right_end)
		temp[pos++] = Arr[j++];
	for (i = left; i <= right_end; i++)
		Arr[i] = temp[i];
	return;
}

Merge Sort는 데이터의 양을 1/2로 분할하기 때문에, 데이터를 분할하는 과정의 시간 복잡도는 O(log N)이다. 그 뒤, 데이터를 합치고 정렬 과정에서 O(N)만큼의 데이터의 복사가 이루어지므로, 총 시간 복잡도는 O(N log N)이 된다.