병합 정렬(Merge Sort)

개념 요약

• 분할 정복을 통해 구현한다.
• 빠른 정렬로 분류되며 퀵 정렬같이 많이 언급된다.
• 정렬되지 않은 배열을 각각 하나의 원소만 포함하는 n개로 분할한다.(결국 원소 하나씩 분할)
• 분할했던 역순으로 정렬하면서 병합한다.

 

---

정렬 과정

1. 배열의 길이가 1이라면 정렬된 것으로 본다.
2. 가져온 배열을 이등분하여 분할한다.
3. 분할한 배열을 재귀적으로 다시 분할한다.
4. 위 과정에서 이등분한 배열을 다시 하나의 정렬된 배열로 합병한다.(임시 배열)
5. 임시 배열의 결과를 원래 배열에 복사한다.

 

---

코드

void	merge(std::vector<int> &unsorted_array, int left, int mid, int right)
{
	// 임시로 사용할 vector 정의
	std::vector<int>	left_array, right_array;
	for (int idx = left; idx < right + 1; ++idx)
	{
		if (idx < mid + 1)
			left_array.push_back(unsorted_array[idx]);
		else
			right_array.push_back(unsorted_array[idx]);
	}
	int	i = 0, j = 0, k = left;
	while (i < left_array.size() && j < right_array.size())
	{
		// 대소비교를 통해 원래 vector에 삽입
		if (left_array[i] < right_array[j])
			unsorted_array[k++] = left_array[i++];
		else
			unsorted_array[k++] = right_array[j++];
	}
	// 남은것들 삽입
	while (i < left_array.size())
		unsorted_array[k++] = left_array[i++];
	while (j < right_array.size())
		unsorted_array[k++] = right_array[j++];
}

void	merge_sort(std::vector<int> &unsorted_array, int left, int right)
{
	if (left < right)
	{
		// 증긴깂 결정
		int	mid = (right + left) / 2;
        // 분할
		merge_sort(unsorted_array, left, mid);
		merge_sort(unsorted_array, mid + 1, right);
		// 정복, 결합
		merge(unsorted_array, left, mid, right);
	}
}

 

---

시간 복잡도

• 평균, 최선, 최악 모두 $O(nlogn)$를 갖는다.

---

공간 복잡도

• $O(n)$

---

장단점

• 효율적이며 안정적인 정렬 방식이다.
• 연결 리스트로 저장 시 유리하다.
• 정복, 결합과정에서 임시 배열이 필요하다.