[알고리즘] MergeSort

mergesort(A[],p,r){
    if(p<r) then{
        q <- (q+p)/2;       //p,q 중간지점 계산
        mergesort(A,p,q);   //전반부 정렬
        mergesort(A,q+1,r); //후반부 정렬
        merge(A,p,q,r);     //병합 (오버헤드 부분)
    }
}
merge(A[],p,q,r){
    //정렬되어있는 두 배열 A[p ~ q]와 A[q+1 ~ r]을 합하
    //정렬된 하나의 배열 A[p ~ r]을 만든다.
}

수행시간의 점화식 : T(n) = 2T(n/2) + 오버헤드
(**오버헤드 : 어떤 명령을 처리하는데 소비되는 간접, 추가적인 자원**)

 

<실제 구현>

#include <iostream>
#include <random>
#define SIZE 10
using namespace std;
int A[SIZE];

void print_arr() {
	for (int i = 0; i < SIZE; i++) {
		cout << A[i] << ' ';
	}
	cout << endl;
}

void Merge(int left, int mid, int right) {
	int i, j, k;

	i = left;
	j = mid + 1;
	k = left;

	int tmp_arr[SIZE];

	// left 부터 mid 까지의 블록과 mid + 1 부터 right 까지의 블록을 서로 비교
	while (i <= mid && j <= right) {
		if (A[i] <= A[j]) {
			tmp_arr[k] = A[i];
			i++;
		}
		else {
			tmp_arr[k] = A[j];
			j++;
		}
		k++;
	}

	// left 블록의 값이 다 처리되었지만, right 블록의 index가 남아 있는 경우
	// right 블록의 남은 부분을 순차적으로 tmp_arr에 복사
	if (i > mid) {
		for (int m = j; m <= right; m++) {
			tmp_arr[k] = A[m];
			k++;
		}
	}
	// left 블록의 남은 부분을 순차적으로 tmp_arr에 복사
	else {
		for (int m = i; m <= mid; m++) {
			tmp_arr[k] = A[m];
			k++;
		}
	}

	// 임시 배열인 tmp_arr의 값을 원본 배열에 복사한다.
	for (int m = left; m <= right; m++) {
		A[m] = tmp_arr[m];
	}

}
void MergeSort(int left, int right) {
	int mid;
	if (left < right) {
		mid = (left + right) / 2;		//중간지점 계산
		MergeSort(left, mid);		//전반부 정렬
		MergeSort(mid + 1, right);	//후반부 정렬
		Merge(left, mid, right);	//병합 (오버헤드 부분)
	}
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	
	for (int i = 0; i < SIZE; i++) {
		A[i] = rand() % 10;
	}
	print_arr();
	MergeSort(0, SIZE - 1);
	print_arr();
	return 0;
}

 

<결과>

참고 : https://jongmin92.github.io/2017/11/06/Algorithm/Concept/merge-sort/