병합 정렬(Merge Sort)

병합 정렬(merge sort) 알고리즘의 개념

• ‘존 폰 노이만(John von Neumann)’이 제안한 방법
• 일반적인 방법으로 구현했을 때 이 정렬은 안정 정렬 에 속하며, 분할 정복 알고리즘이다.
  • 분할 정복(divide and conquer) 방법
    • 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결함
    • 분할 정복 방법은 대개 순환 호출을 이용하여 구현.

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

병합 정렬(Merge Sort) C++ 코드

#include <iostream>
#include <vector>
using namespace std;

vector<int> sorted;
// i: 정렬된 왼쪽 리스트에 대한 인덱스
// j: 정렬된 오른쪽 리스트에 대한 인덱스
// k: 정렬될 리스트에 대한 인덱스
/* 2개의 인접한 배열 list[left...mid]와 list[mid+1...right]의 합병 과정 */
/* (실제로 숫자들이 정렬되는 과정) */
void Merge(vector<int>& v,int start,int mid,int end)
{
	int i = start;
	int j = mid + 1;
	int k = start;
	//분할 정렬된 리스트 합병
	while (i <= mid && j <= end)
	{
		if (v[i] <= v[j])
		{
			sorted[k] = v[i];
			i++;
		}
		else
		{
			sorted[k] = v[j];
			j++;

		}
		k++;
	}

	int entry = (i > mid) ? j:i;
	int target= (i > mid) ? end : mid;
	//남아 있는 값들 복사 
	for (int t = entry; t <= target; ++t)
	{
		sorted[k] = v[t];
		k++;
	}
	//정렬된 임시 리스트를  원래 리스트에 복사 
	for (int t = start; t <= end; ++t)
	{
		v[t] = sorted[t];
	}



}

void MergeSort(vector<int>& v, int start, int end)
{
	if (sorted.size() == 0)
	{
		sorted= vector<int>(v.size());
	}
	if (start < end)
	{
		int mid = (start + end) / 2;  // 중간 위치를 계산하여 리스트를 균등 분할 -분할(Divide)
		MergeSort(v, start, mid);  // 중간 위치를 계산하여 리스트를 균등 분할 -분할(Divide)
		MergeSort(v, mid + 1, end); // 중간 위치를 계산하여 리스트를 균등 분할 -분할(Divide)
		Merge(v,start, mid,end); // 정렬된 2개의 부분 배열을 합병하는 과정 -결합(Combine)


	}
}


int main()
{
	vector<int> v = { 5,4,3,2,1 };
	MergeSort(v, 0, v.size() - 1);
	for (auto& e : v)
	{
		cout << e;

	}


	return 0;
}