병합 정렬 - 분할 정복, 시간 복잡도

※ 웹 환경에 최적화된 서식이므로 웹 페이지로 열람함을 권장.

 

병합 정렬

주어진 배열을 크기가 1 이 될 때까지 절반씩 나눈다. 길이 1짜리 수열들을 서로 합치는 과정에서 크기를 비교해 정렬한다.

 

실제로 배열을 나누는 과정은 인덱스의 위치를 조정하는 것으로 O(1) 에 수행되고 나뉜 배열을 합치는 과정에서 각 원소 모두를 비교해 정렬한다. 즉, n 개 배열에 대해 O(n) 의 비교 과정을 거친다.

 

나눠진 배열을 합치는 과정을 원본 배열이 나눠진 횟수만큼 반복해야 한다. 길이가 n 인 원본 배열을 항상 거의 절반으로 나누므로 나눠진 횟수는 로그 n 이다. 따라서, 병합 정렬의 시간 복잡도는 O(n * lgn).

 

자세한 구현은 코드의 주석으로 확인해보자.

 

vector<int> v, tmp;

void mergeSort(int lo, int hi) {
	if (lo >= hi) return;

	int mid = (lo + hi) / 2;
	mergeSort(lo, mid);
	mergeSort(mid + 1, hi);
	
    // i: 앞 배열을 하나씩 가리키는 인덱스.
    // j: 뒷 배열을 하나씩 가리키는 인덱스.
    // k: 정렬된 상태로 원소를 저장할 임시 배열의 인덱스.
	int i = lo, j = mid + 1, k = lo; 

	// i 가 앞 배열의 끝인 mid 를 넘거나 
    // j 가 뒷 배열의 끝인 hi 를 넘으면 종료.
	while (i <= mid && j <= hi) {
    	// i 위치와 j 위치의 원소를 비교해 작은 것부터
        // 임시 배열의 k 에 저장. (각 인덱스를 증가해 가며 수행)
		if (v[i] < v[j]) tmp[k++] = v[i++]; 
		else tmp[k++] = v[j++];
	}

	// 앞 혹은 뒤 배열 중 하나만 임시 배열로 복사를 완료하므로
    // 어느 배열에 복사할 원소가 남았는지 확인해 복사를 마친다.
	int l = (i > mid) ? j : i;
	while (k <= hi) { tmp[k++] = v[l++]; }

	// 임시 배열에 lo 부터 hi 까지 정렬된 상태로 저장했으므로
    // 원본 배열의 같은 위치에 복사한다.
	for (l = lo; l <= hi; ++l) v[l] = tmp[l];
}

int main() {
	v = vector<int> {9,8,7,6,5,4,3,2};
	tmp = vector<int> (v.size());

	mergeSort(0, v.size() - 1);
			
	return 0;
}