[알고리즘/C++] 병합 정렬(merge sort)

병합 정렬(merge sort)는 배열을 절반씩 쪼개서 재귀적인 방법으로 Sorting하는 알고리즘이다. 

 

병합 정렬(merge sort)

void merge(vi& arr, int low, int mid, int high) {
	vi ans;

	int i = low;
	int j = mid + 1;
	while (i <= mid && j <= high) {
		if (arr[i] < arr[j]) {
			ans.push_back(arr[i++]);
		}
		else {
			ans.push_back(arr[j++]);
		}
	}

	if (i > mid) {
		while (j <= high) {
			ans.push_back(arr[j++]);
		}
	}

	if (j > high) {
		while (i <= mid) {
			ans.push_back(arr[i++]);
		}
	}

	int k = 0;
	for (int i = low; i <= high; i++) {
		arr[i] = ans[k++];
	}
}

먼저 배열이 절반씩 쪼개져서 원소 하나를 갖는 수준으로 쪼개진다. 

 

그러나서 두 배열끼리 합치는데 합치는 기준은 첫번째 배열과 두번째 배열의 원소 하나하나를 비교해서 작은 것부터 

 

임시 배열에 채운다. 

 

위의 그림의 예에서 3  7 과  2  16 을 merge할 경우에 

 

먼저 3과 2를 비교해서 2가 더 작으므로 2를 채우고, 그 다음 3, 그 다음 7을 채우면 

 

첫번째 배열은 모두 소진했으므로 두번째 배열의 나머지 원소들을 다 채워준다. 

 

그리고 이 정렬된 임시 배열(ans)의 값들을 원래의 배열(arr)에 그대로 복붙해준다. 

 

merge 함수에 있는 low, mid, high의 역할은 원본 배열 arr에서의 위치를 잡기 위해서 존재한다. 

 

실제로 두 배열을 합치는 것은 아니고, 원본 배열의 일부분(low ~ mid / mid+1 ~ high) 끼리의 비교를 통해서 

 

배열을 합쳐서 정돈하는 것처럼 보인다. 

 

void mergeSort(vi& arr, int low, int high) {
	if (low < high) {
		int mid = (low + high) / 2;
		mergeSort(arr, low, mid);
		mergeSort(arr, mid + 1, high);
		merge(arr, low, mid, high);
		printVector(arr);
	}
}

low가 high보다 작을 동안 배열의 분할이 이루어지며, low와 high가 같은 경우, 즉 원소가 하나일 경우에는 

 

원본 배열에 아무 일도 일어나지 않으며, 바로 재귀를 호출한 함수로 거슬러 올라가서 merge된다. 

 

int main() {
	vector<int> arr = { 6,4,3,2,1,1,5,999,11};
	mergeSort(arr, 0, arr.size()-1);
}

mergeSort를 호출한 결과이다. sort되는 과정을 보여준다.

4 6 3 2 1 1 5 999 11
3 4 6 2 1 1 5 999 11
3 4 6 1 2 1 5 999 11
1 2 3 4 6 1 5 999 11
1 2 3 4 6 1 5 999 11
1 2 3 4 6 1 5 11 999
1 2 3 4 6 1 5 11 999
1 1 2 3 4 5 6 11 999