3-2 정렬(Merge Sort)

병합 정렬(Merge Sort)은 분할 정복 방식을 사용해 데이터를 분할하고 분할한 집합을 정렬하며 합치는 알고리즘이다.

병합 정렬의 시간 복잡도는 O(nlogn)이고, 임시로 배열의 값을 저장할 추가 메모리가 요구된다.

 

이미지 출처:https://gmlwjd9405.github.io/2018/05/08/algorithm-merge-sort.html

 

두 포인터 개념을 사용하여 왼쪽, 오른쪽 그룹을 병합한다.

왼쪽 포인터와 오른쪽 포인터의 값을 비교하여 작은 값을 결과 배열에 추가하고 포인터를 오른쪽으로 1칸 이동시킨다.

 

#include <iostream>
#include <vector>

using namespace std;

void mergeSort(vector<int>&, int, int);
int main() {
	cin.tie(0)->sync_with_stdio(false);

	int N;
	cin >> N;
	vector<int> arr(N, 0);

	for (int i = 0; i < N; ++i) {
		cin >> arr[i];
	}

	mergeSort(arr, 0, N - 1);

	for (auto& it : arr)
		cout << it << '\n';

	return 0;
}

void mergeSort(vector<int>& arr, int s, int e) {
	static vector<int>tmp = arr;
	if (e - s < 1) {
		return;
	}
	int m = (s + e) / 2;
	mergeSort(arr, s, m);
	mergeSort(arr, m + 1, e);

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

	int i = s;
	int j = m + 1;
	while (i <= m && j <= e) {
		if (tmp[i] < tmp[j]) {
			arr[s++] = tmp[i++];
		}
		else {
			arr[s++] = tmp[j++];
		}
	}

	while (i <= m) arr[s++] = tmp[i++];
	while(j <= e) arr[s++] = tmp[j++];
}