병합(합병) 정렬 (C/C++ 구현, 시간 복잡도)

1. 병합정렬

 합병 정렬 또는 병합 정렬(merge sort)은 O(n log n) 비교 기반 정렬 알고리즘이다. 일반적인 방법으로 구현했을 때 이 정렬은 안정 정렬에 속하며, 분할 정복 알고리즘의 하나이다. 존 폰 노이만이 1945년에 개발했다.

합병 정렬 - 위키백과, 우리 모두의 백과사전

출처 - 위키피디아(https://ko.wikipedia.org/wiki/%ED%95%A9%EB%B3%91_%EC%A0%95%EB%A0%AC)

나의 해석 : 반으로 분할 -> 합병(합칠 때 크기 비교)

 

 

요구 사항

1. 배열 오름차순으로 구현

 

풀이 방법

1. 최소 단위까지 분할 - 재귀

2. 합병 할 때 크기 비교하여 임시 배열에 넣음(소스 코드 참조)

3. 임시 배열을 다시 원래 배열로 옮김

 

시간 복잡도

최소 단위가 될 때까지 분할 log n

합병하면서 비교 n

O(nlogn)

 

 

 

소스 코드

#include <iostream>

using namespace std;
int a[10] = { 5,4,3,2,1 ,457,5412,879456,45120,6523};

//합치기
void m_sort(int list[], int l, int m, int r)
{
	int i, j, k;
	i = l;
	j = m + 1;
	k = l;
	int temp[11];
	//왼쪽에서 정렬된 배열과 오른쪽에서 정렬된 배열을 합침
	//둘중 하나가 끝까지 올때 까지 합침
	while (i <= m && j <= r)
	{
		if (list[i] <= list[j])
			temp[k++] = list[i++];
		else
			temp[k++] = list[j++];
	}
	//오른쪽 배열에 임시 배열로 추가할 수가 남았으면 오른쪽 배열을 임시 배열로 복사
	if (i > m)
	{
		for (int x = j; x <= r; x++)
			temp[k++] = list[x];
	}
	//왼쪽 배열에 임시 배열로 추가할 수가 남았으면 왼쪽 배열을 임시 배열로 복사
	else
	{
		for (int x = i; x <= m; x++)
			temp[k++] = list[x];
	}

	//본 배열으로 복귀
	for (int x = l; x <= r; x++)
		list[x] = temp[x];
}
void merge(int list[], int l, int r)
{
	int mid;
	if (l < r)
	{
		mid = (l + r) / 2;
		merge(list, l, mid);
		merge(list, mid + 1, r);
		m_sort(list, l, mid, r);
	}
}
int main()
{
	merge(a,0,9);
	for (int i = 0; i < 10; i++)
	{
		cout << a[i] << " ";
	}
	return 0;
}