[알고리즘] 병합 정렬(Merge Sort)

 

 

병합 정렬

  병합 정렬은 분할 정복 방식을 사용해 데이터를 분할하고 분할한 집합을 정렬하며 합치는 알고리즘으로, 시간 복잡도는 O(nlogn)이다. 투 포인터 개념을 사용하여 배열의 원소를 나누며, 왼쪽, 오른쪽 그룹을 병합해간다. 왼쪽 포인터와 오른쪽 포인터의 값을 비교하여 작은 값(혹은 큰 값)을 배열에 추가하고, 포인터를 한 칸씩 이동시키는 방식이다.

  합병 정렬 또는 병합 정렬(영어: merge sort 머지 소트[*])은 O(n log n) 비교 기반 정렬 알고리즘이다. 일반적인 방법으로 구현했을 때 이 정렬은 안정 정렬에 속하며, 분할 정복 알고리즘의 하나이다. (위키백과 발췌)

 

 

n-way 합병 정렬의 개념은 다음과 같다.

1. 정렬되지 않은 리스트를 각각 하나의 원소만 포함하는 n개의 부분리스트로 분할한다.
   (한 원소만 든 리스트는 정렬된 것과 같으므로)
2. 부분리스트가 하나만 남을 때까지 반복해서 병합하며 정렬된 부분리스트를 생성한다.
   마지막 남은 부분리스트가 정렬된 리스트이다.

 

 

 

 

 

구현 코드

void MergeSort(int start, int end)
{
	if (end - start < 1)
		return;
	int middle = start + (end - start) / 2;
	MergeSort(start, middle);
	MergeSort(middle + 1, end);

	for (int i = start; i <= end; i++)
		temp[i] = nums[i];

	int k = start;
	int idx1 = start, idx2 = middle + 1;

	while (idx1 <= middle && idx2 <= end)
	{
		if (temp[idx1] < temp[idx2])
			nums[k++] = temp[idx1++];
		else nums[k++] = temp[idx2++];
	}

	while (idx1 <= middle)
		nums[k++] = temp[idx1++];
	while (idx2 <= end)
		nums[k++] = temp[idx2++];
}

 

 

 

 

 

 

참고

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