병합 정렬

병합정렬(Merge Sort)은 분할 정복(divide and conquer) 알고리즘 중 하나로,

주어진 배열을 반으로 나누고, 각 부분 배열을 재귀적으로 정렬하며,

정렬된 부분 배열을 병합하여 전체 배열을 정렬하는 방식입니다.

 

아래는 병합정렬의 구체적인 과정입니다.

1. 주어진 배열을 반으로 나눕니다. 이때, 배열의 크기가 1 이하가 될 때까지 계속해서 반으로 나누어줍니다.
2. 각 부분 배열을 정렬합니다. 이때, 재귀적으로 정렬을 수행합니다.
3. 정렬된 부분 배열을 병합합니다. 병합할 때는 각 부분 배열의 첫번째 원소를 비교하여 작은 값부터 새로운 배열에 추가해줍니다.
4. 전체 배열이 정렬될 때까지 위 과정을 반복합니다.

아래는 C++ 코드로 구현한 병합정렬 예시입니다.

#include <iostream>
#include <vector>

using namespace std;

void merge_sort(int s, int e);
static vector<int> A;
static vector<int> tmp;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N;
	cin >> N;
	A = vector<int>(N + 1, 0);
	tmp = vector<int>(N + 1, 0);

	for (int i = 1; i <= N; i++)
		cin >> A[i];

	result = 0;
	merge_sort(1, N);

	for (int i = 1; i < A.size(); i++)
		cout << A[i] << " ";
		
}

void merge_sort(int start, int end)
{
	if (end - start < 1) return;

	int mid = start + (end - start) / 2;
	merge_sort(start, mid);
	merge_sort(mid + 1, end);

	for (int i = start; i <= end; i++)
		tmp[i] = A[i];

	int k = start; 
	int i = start;
	int j = mid + 1;

	while (i <= mid && j <= end)
	{
		if (tmp[i] > tmp[j])
		{
			A[k] = tmp[j];
			k++;
			j++;
		}
		else
		{
			A[k] = tmp[i];
			k++;
			i++;
		}
	}

	while (i <= mid)
		A[k++] = tmp[i++];

	while (j <= end)
		A[k++] = tmp[j++];
}

위 코드에서 merge_sort 함수는 주어진 배열을 두 부분으로 나누고,

각 부분 배열을 재귀적으로 정렬한 뒤, merge 함수를 호출하여 두 부분 배열을 병합합니다.

merge 함수에서는 각 부분 배열의 첫번째 원소를 비교하여 작은 값부터 새로운 배열에 추가합니다.

이러한 과정을 반복하여 전체 배열이 정렬된 결과를 반환합니다.