[알고리즘] 합병정렬 (Merge Sort) (BOJ 2752, C++)

💡 합병 정렬(Merge Sort)이란?

합병 정렬(Merge Sort)은 분할 정복(divide and conquer) 방식을 사용한 대표적인 정렬 알고리즘이에요. 데이터를 반으로 나누고, 나눈 데이터를 정렬하면서 다시 합치는 과정을 반복해 정렬을 완성합니다.

쉽게 말해, 작게 나눠서 해결한 뒤, 다시 합치는 방법이라고 이해하면 됩니다.

---

✨ 합병 정렬의 원리

합병 정렬은 다음 세 단계로 이루어져 있어요.

1️⃣ 분할(Divide)

정렬할 배열을 두 개의 작은 배열로 나눕니다.
이 과정을 배열의 크기가 1이 될 때까지 반복해요.

2️⃣ 정복(Conquer)

나눠진 배열을 각각 정렬합니다.
여기서 정렬은 재귀적으로 이루어지며, 각 배열이 하나씩 정렬된 상태로 만들어져요.

3️⃣ 합병(Merge)

정렬된 배열 두 개를 비교하여 하나의 배열로 합칩니다.
이때, 두 배열의 가장 작은 값부터 차례로 비교하며 정렬된 순서로 넣어줍니다.

---

🛠️ 합병 정렬의 동작 과정 (예제)

예를 들어 [8, 4, 7, 2, 5, 1, 6, 3] 배열을 정렬한다고 해볼게요.

1️⃣ 분할 단계

• 배열을 계속 반으로 나눕니다.
  [8, 4, 7, 2, 5, 1, 6, 3] → [8, 4, 7, 2], [5, 1, 6, 3]
  → [8, 4], [7, 2], [5, 1], [6, 3]
  → [8], [4], [7], [2], [5], [1], [6], [3]

2️⃣ 정렬 후 합병 단계

• 가장 작은 단위부터 차례로 합치며 정렬합니다.
  • [8]과 [4] → [4, 8]
  • [7]과 [2] → [2, 7]
  • [5]과 [1] → [1, 5]
  • [6]과 [3] → [3, 6]

3️⃣ 최종 정렬된 배열 생성

• 다시 정렬된 배열들을 합칩니다.
  • [4, 8]과 [2, 7] → [2, 4, 7, 8]
  • [1, 5]과 [3, 6] → [1, 3, 5, 6]
  • [2, 4, 7, 8]과 [1, 3, 5, 6] → [1, 2, 3, 4, 5, 6, 7, 8]

---

🔍 합병 정렬의 특징

✅ 장점

1. 안정 정렬: 동일한 값의 순서가 유지됩니다.
2. 시간 복잡도가 안정적: 최선, 평균, 최악의 경우 모두 **O(n log n)**입니다.
3. 대량의 데이터를 정렬할 때 효율적입니다.

❌ 단점

1. 추가 메모리 공간 필요: 임시 배열을 사용해야 해서 **O(n)**의 추가 메모리를 사용합니다.
2. 데이터 크기가 작을 경우 다른 정렬보다 느릴 수 있습니다.

 

도움되는 문제 : https://www.acmicpc.net/problem/2751

 

합병정렬 코드를 직접 짜보았습니다.

#include <iostream>
using namespace std;
void mergesort(int ary[], int left, int right);
int main()
{
	int n;
	cin >> n;
	int* ary = new int[n];
	for (int i = 0; i < n; i++)
	{
		cin >> ary[i];
	}
	mergesort(ary, 0, n - 1);
	for (int i = 0; i < n; i++)
		cout << ary[i] << '\n';
	delete[]ary;
	return 0;
}
void mergesort(int ary[], int left, int right) {
	if (left >= right) return;
	int mid = (left + right) / 2;
	mergesort(ary, left, mid);
	mergesort(ary, mid + 1, right);
	int n1 = mid - left + 1;
	int n2 = right - mid;
	int* leftArr = new int[n1];
	int* rightArr = new int[n2];
	for (int i = 0; i < n1; i++)
		leftArr[i] = ary[left + i];
	for (int i = 0; i < n2; i++)
		rightArr[i] = ary[mid + 1 + i];
	int i = 0, j = 0, k = left;
	while (i < n1 && j < n2) {
		if (leftArr[i] <= rightArr[j])
			ary[k++] = leftArr[i++];
		else
			ary[k++] = rightArr[j++];
	}
	while (i < n1)
		ary[k++] = leftArr[i++];
	while (j < n2)
		ary[k++] = rightArr[j++];

	delete[]leftArr;
	delete[]rightArr;
}