[C++] 병합(Merge Sort)

병합정렬

시간복잡도: 평균 = O(nlog(n))

병합정렬은 분할정복 개념을 알고있어야 구현가능합니다.

어떠한 문제를 잘게 쪼게어 다시 조합하는 방식의 문제 해결 방법입니다.

분할정복은 보통 재귀 호출을 이용하여 구현합니다.

처음 정렬할 요소들을 쪼게고 해당 단계에서는 이동연산과 비교연산을 하지 않습니다.

 

*계속 둘로 쪼갠 횟수만큼 n번만큼 반복

#include <iostream>
#include <vector>

using namespace std;

int S[100001];

void merge(int low, int mid, int high) {
	vector<int>u;
	int i = low;
	int j = mid + 1;
	while (i <= mid && j <= high) {
		if (S[i] < S[j]) {
			u.push_back(S[i]);
			i++;
		}
		else {
			u.push_back(S[j]);
			j++;
		}
	}
	for (int t = j; t <= high; t++)
		u.push_back(S[t]);
	for (int t = i; t <= mid; t++)
		u.push_back(S[t]);
	for (int t = low; t <= high; t++)
		S[t] = u[t - low];
}

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