합병 정렬(Merge sort)

머지 소트, 합병 정렬 여러가지 이름으로 존재한다.
이해하면서 분할합병 정렬? 이라고 하는게 옳지 않나 싶다.

제일 먼저 합병 정렬에 큰 도움을 받은 블로그의 링크를 올려 놓는다.
링크 : https://gmlwjd9405.github.io/2018/05/08/algorithm-merge-sort.html

[알고리즘] 합병 정렬(merge sort)이란 - Heee's Development Blog

합병 정렬은 '존 폰 노이만' 사람이 제안한 방법
-> 컴퓨터 구조를 배우면 먼저 볼 수 있는 사람.

합병 정렬은 분할 정복 알고리즘의 하나이다.
-> 분할 정복 이란
    -> 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략
    -> 분할 정복 방법은 대개 재귀 함수를 이용하여 구현

※합병 정렬 과정
1. 리스트의 길이가 0 또는 1 이면 이미 정렬된 것으로 본다. 그렇지 않은 경우에는,
2. 정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다.
3. 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬
4. 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병

합병 정렬 단계
- 분할 : 입력 배열을 같은 크기의 2개의 부분 배열로 분할
- 정복 : 부분 배열을 정렬
- 결합 : 정렬된 부분 배열들을 하나의 배열에 합병

합병 정렬의 특징
- 추가적인 리스트가 필요
- 각 부분 배열을 정렬할 때도 합병 정렬을 순환적으로 호출하여 적용
- 합병 정렬에서 실제로 정렬이 이루어지는 시점은 2개의 리스트를 합병하는 단계이다.

#include <iostream>

#define MAX_SIZE 8	

using namespace std;

int sorted[MAX_SIZE];

void merge(int list[], int left, int mid, int right)
{
	int i, j, k, l;

	i = left;
	j = mid + 1;
	k = left;

	while (i <= mid && j <= right)
	{
		if (list[i] <= list[j])
		{
			sorted[k++] = list[i++];
		}
		else
		{
			sorted[k++] = list[j++];
		}
	}

	if (i > mid)
	{
		for (l = j; l <= right; l++)
		{
			sorted[k++] = list[l];
		}
	}
	else
	{
		for (l = i; l <= mid; l++)
		{
			sorted[k++] = list[l];
		}
	}

	for (l = left; l <= right; l++)
	{
		list[l] = sorted[l];
	}
}
void mergesort(int list[], int left, int right)
{
	int mid;


	if (left < right)
	{
		mid = (left + right) / 2;
		mergesort(list, left, mid);
		mergesort(list, mid + 1, right);

		merge(list, left, mid, right);
	}
}

int main(void)
{
	int n = MAX_SIZE;
	int nList[MAX_SIZE] = { 21, 10, 12, 20, 25, 13, 15, 22 };

	mergesort(nList, 0, n - 1);

	for (int i = 0; i < n; i++)
	{
		cout << nList[i] << " ";
	}
	return 0;
}