백준 1517번 [버블 소트]

병합 정렬(분할 정복)

 

nlogn 정렬을 sort()가 아닌 직접 구현해야 할 때(과정을 봐야할 때) ㅡ> 병합 정렬

vector<int> v;
vector<int> tmp;
ll res = 0;

void merge_sort(int s, int e) {
	if (e - s < 1) {
		return;
	}

	int m = s + (e - s) / 2;

	merge_sort(s, m);
	merge_sort(m + 1, e);

	for (int i = s; i <= e; i++) {
		tmp[i] = v[i];
	}

	int k = s;
	int index1 = s;
	int index2 = m + 1;

	while (index1 <= m && index2 <= e) {
		if (tmp[index1] > tmp[index2]) {
			v[k] = tmp[index2];
			k++;
			index2++;
			res += (index2 - k);
		}
		else {
			v[k] = tmp[index1];
			k++;
			index1++;
		}
	}

	while (index1 <= m) {
		v[k] = tmp[index1];
		k++;
		index1++;
	}
	while (index2 <= e) {
		v[k] = tmp[index2];
		k++;
		index2++;
	}
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	int n;
	cin >> n;
	v = vector<int>(n, 0);
	tmp = vector<int>(n, 0);

	for (int i = 0; i < n; i++) {
		int x;
		cin >> x;
		v[i] = x;
	}
	merge_sort(0, n - 1);

	cout << res;

	return 0;
}