MergeSort구현

MergeSort를 구현했습니다.

각 함수별 기능 설명

Merge : 분할된 두 부분을 합쳐주는 기능을합니다.

MergeSort : 분할 정복을 이용해서 각각 Sort를 실행하는 함수입니다.

위 사진과 같이 분할 정복을 통해서 머지소트가 실행됩니다.

Worst Case time Complexity

머지소트의 최악수행시간의 점화식은

W(n) = W(n/2) + W(n/2) + W(merge)(n)입니다.

이를 Master theorem을 이용해서 점화식을 풀면

O(nlogn)이라는 최악수행시간이 나옵니다.

즉 MergeSort의 최악수행시간 = O(nlogn)

#include 
#include 
using namespace std;

void Merge(vector& arr,int start, int mid, int end) {
	int first = start;
	int second = mid + 1;
	int pos = start;
	vector temp = arr;

	while (first <= mid && second <= end) {
		if (temp[first] <= temp[second]) {
			arr[pos++] = temp[first++];
		}
		else {
			arr[pos++] = temp[second++];	
		}
	}

	if (first > mid) {
		for (int i = second; i <= end; i++) {
			arr[pos++] = temp[i];
		}
	}
	else {
		for (int i = first; i <= mid; i++) {
			arr[pos++] = temp[i];
		}
	}
	
	return;

}

void MergeSort(vector& arr, int start, int end) {
	if (start < end) {
		int mid = (start + end) / 2;

		MergeSort(arr, start, mid);
		MergeSort(arr, mid + 1, end);
		Merge(arr, start, mid, end);
	}
}

int main() {
	std::ios::sync_with_stdio(false);
	vector arr;
	int C, n;

	cin >> C;

	for (int i = 0; i < C; ++i) {
		cin >> n;
		arr.push_back(n);
	}

	MergeSort(arr, 0, C - 1);

	for (int i = 0; i < C; ++i) {
		cout << arr[i] << " ";
	}
	cout << endl;

	arr.clear();
	return 0;
}