알고리즘 - 합병 정렬

- merge sort

- 분할 정복(divide and conquer) 방법, 보통 재귀를 이용하여 구현

- 분할(divide): 입력 배열을 같은 크기의 2개의 부분 배열로 분할한다.
  정복(conquer): 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 순환 호출을 이용하여 다시 분할 정복 방법 적용
  결합(combine): 정렬된 부분 배열들을 하나의 배열에 합병

- 시간복잡도 분석
 : 배열이 부분 배열로 나누어지는 단계에서는 비교 연산이나 이동 연산이 수행되지 않는다. 재귀 호출의 깊이는 
 : 합병단계에서 비교 연산 최대 n번, 임시 배열에 복사했다가 다시 가져와야하는 이동 연산 n 번으로 총 2n번 레코드의 이동 발생
 : 총 시간 복잡도는 

- 입력 데이터가 무엇이든 간에 정렬되는 시간은 동일 (데이터의 분포에 영향을 덜 받는 안정적인 정렬 방법)

- 단점으로
  : 임시 배열이 필요함
  : 레코드들의 크기가 큰 경우에는 이동 횟수가 많으므로 매우 큰 시간적 낭비를 초래 -> 연결리스트로 극복

- CODE

#include <iostream>
using namespace std;

int arr[1000001];
int save[1000001];

void merge_sort(int* a, int start, int end) {
	if (start == end) {
		return;
	}
	else if (start + 1 == end) {
		if (a[start] > a[end]) {
			swap(a[start], a[end]);
		}
		return;
	}

	// divide
	int mid = (start + end) / 2;
	merge_sort(a, start, mid);
	merge_sort(a, mid + 1, end);
	int left = start;
	int right = mid + 1;
	int k = 0;

	// conquer
	while (left <= mid && right <= end) {
		if (a[left] <= a[right]) {
			save[k++] = a[left++];
		}
		else {
			save[k++] = a[right++];
		}
	}
	while (left <= mid) {
		save[k++] = a[left++];
	}
	while (right <= end) {
		save[k++] = a[right++];
	}

	// combine
	for (int i = start; i <= end; i++) {
		a[i] = save[i - start];
	}
}

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

	merge_sort(arr, 0, n - 1);

	for (int i = 0; i < n; i++)
		cout << arr[i] << "\n";

	return 0;
}