[CS50] 알고리즘 - 병합 정렬

병합 정렬(Merge Sort)은 원소가 한 개가 될 때까지 계속 반으로 나누다가 다시 합쳐나가며 정렬하는 방식이다.

이 과정은 재귀적으로 구현된다.

동작 원리

다음 숫자들을 오름차순으로 정렬해보자.

7 4 5 2 6 3 8 1

 

1단계: 분할

숫자들을 반으로 계속 나눈다.

7 4 5 2 | 6 3 8 1

7 4 | 5 2 | 6 3 8 1

7 | 4 | 5 2 | 6 3 8 1

 

원소가 한 개가 될 때까지 나눈다.

7 | 4 | 5 | 2 | 6 | 3 | 8 | 1

 

2단계: 병합

이제 작은 숫자가 먼저 오도록 병합한다.

숫자 1개씩 병합:

4 7 | 2 5 | 3 6 | 1 8

 

숫자 2개씩 병합:

• 4 7과 2 5를 병합: 2와 4 비교 → 2, 4와 5 비교 → 4, 7과 5 비교 → 5, 7 남음

2 4 5 7 | 1 3 6 8

 

숫자 4개씩 병합:

• 2 4 5 7과 1 3 6 8을 병합
• 각 부분의 앞에서부터 비교하여 작은 값을 가져옴

1 2 3 4 5 6 7 8

 

전체 과정 요약:

7 | 4 | 5 | 2 | 6 | 3 | 8 | 1    →  가장 작은 부분 (숫자 1개)

4   7 | 2   5 | 3   6 | 1   8    →  숫자 1개씩 정렬하여 병합

2   4   5   7 | 1   3   6   8    →  숫자 2개씩 정렬하여 병합

1   2   3   4   5   6   7   8    →  숫자 4개씩 정렬하여 병합

 

시간 복잡도

분할 단계:

• 배열을 반으로 나누는 과정: O(log n)
• 8개 → 4개 → 2개 → 1개 (3번 분할, log₂8 = 3)

병합 단계:

• 각 단계에서 모든 원소를 비교: O(n)
• 각 레벨마다 n번의 비교

전체 시간 복잡도:

• 상한: O(n log n)
• 하한: Ω(n log n)

정렬 여부와 관계없이 나누고 병합하는 과정이 필요하므로 하한도 동일하다.

O와 Ω가 같은 경우를 Θ(Theta)라고 한다. 병합 정렬의 시간 복잡도는 Θ(n log n)이다.

 

다른 정렬과 비교

정렬 알고리즘	최선	평균	최악
버블 정렬	Ω(n)	-	O(n²)
선택 정렬	Ω(n²)	-	O(n²)
병합 정렬	Ω(n log n)	-	O(n log n)

 

연습 문제

Q. 병합 정렬을 선택 정렬이나 버블 정렬과 비교했을 때 장점과 단점은 무엇이 있을까?
장점:

1. 일관된 성능
   • 최선, 평균, 최악 모두 O(n log n)
   • 데이터 상태와 무관하게 안정적
2. 빠른 속도
   • 데이터 양이 많을 때 O(n²) 정렬보다 훨씬 빠름
   • 예: 100만 개 정렬 시 n² ≈ 1조, n log n ≈ 2000만
3. 안정 정렬
   • 같은 값의 상대적 순서가 유지됨

단점:

1. 추가 메모리 필요
   • 정렬할 배열과 같은 크기의 임시 배열 필요
   • 공간 복잡도: O(n)
2. 작은 데이터에서 비효율
   • 재귀 호출 오버헤드
   • 작은 데이터셋에서는 삽입 정렬이 더 빠를 수 있음

 

특성	버블/선택 정렬	병합 정렬
시간	O(n²)	O(n log n)
공간	O(1)	O(n)
구현	간단	복잡
적합한 경우	소량 데이터	대량 데이터

 

결론:
대량의 데이터를 정렬할 때는 병합 정렬이 훨씬 효율적이지만, 추가 메모리가 필요하다는 단점이 있다.