분할 정복 (Divide and Conquer)
해결하기 힘든 문제가 있다면 한 번에 해결하려 하지 말고, 해결하기 쉬울 정도로 문제를 쪼갠 다음 하나씩 해결하라
이것이 바로 분할 정복(Divide and Conquer) 전략이다. 병합 정렬은 이 전략을 완벽하게 구현한 알고리즘으로 지금까지 알아본 O(n²) 정렬들과는 차원이 다른 O(n log n)의 성능을 자랑한다
병합 정렬이란?
병합 정렬은 배열을 재귀적으로 절반씩 나누어 더 이상 나눌 수 없을 때까지(원소가 1개) 분할한 후, 다시 정렬하면서 병합하는 알고리즘이다
핵심 원리
- 분할(Divide): 배열을 절반으로 나눈다
- 정복(Conquer): 각 부분을 재귀적으로 정렬한다
- 병합(Merge): 정렬된 부분들을 하나로 합친다
동작 과정 상세 분석
배열 [3, 5, 2, 4, 1, 7, 8, 6]을 오름차순으로 정렬하는 과정을 단계별로 살펴보자
═══════════════════════════════════════════════════
레벨 0: 초기 배열 (8개 원소)
═══════════════════════════════════════════════════
[3, 5, 2, 4, 1, 7, 8, 6]
↓ 절반으로 분할
═══════════════════════════════════════════════════
레벨 1: 4개씩 2그룹
═══════════════════════════════════════════════════
[3, 5, 2, 4] [1, 7, 8, 6]
↓ ↓
절반 분할 절반 분할
═══════════════════════════════════════════════════
레벨 2: 2개씩 4그룹
═══════════════════════════════════════════════════
[3, 5] [2, 4] [1, 7] [8, 6]
↓ ↓ ↓ ↓
절반 절반 절반 절반
═══════════════════════════════════════════════════
레벨 3: 1개씩 8그룹 (더 이상 분할 불가)
═══════════════════════════════════════════════════
[3] [5] [2] [4] [1] [7] [8] [6]
✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓
각 원소는 이미 정렬된 상태!
```
### 2단계: 병합 과정 (Merge)
```
═══════════════════════════════════════════════════
레벨 3 → 레벨 2: 1개씩 → 2개씩 병합
═══════════════════════════════════════════════════
[3] + [5] → [3, 5] ✓
[2] + [4] → [2, 4] ✓
[1] + [7] → [1, 7] ✓
[8] + [6] → [6, 8] ✓
결과: [3, 5] [2, 4] [1, 7] [6, 8]
═══════════════════════════════════════════════════
레벨 2 → 레벨 1: 2개씩 → 4개씩 병합
═══════════════════════════════════════════════════
[3, 5] + [2, 4] → [2, 3, 4, 5] ✓
[1, 7] + [6, 8] → [1, 6, 7, 8] ✓
결과: [2, 3, 4, 5] [1, 6, 7, 8]
═══════════════════════════════════════════════════
레벨 1 → 레벨 0: 4개씩 → 8개로 최종 병합
═══════════════════════════════════════════════════
[2, 3, 4, 5] + [1, 6, 7, 8]
병합 과정:
1 < 2 → [1]
2 < 6 → [1, 2]
3 < 6 → [1, 2, 3]
4 < 6 → [1, 2, 3, 4]
5 < 6 → [1, 2, 3, 4, 5]
6만 남음 → [1, 2, 3, 4, 5, 6]
7만 남음 → [1, 2, 3, 4, 5, 6, 7]
8만 남음 → [1, 2, 3, 4, 5, 6, 7, 8]
최종 결과: [1, 2, 3, 4, 5, 6, 7, 8] ✓
재귀 호출 트리 시각화
[3,5,2,4,1,7,8,6]
|
┌──────────────┴──────────────┐
↓ ↓
[3,5,2,4] [1,7,8,6]
| |
┌────┴────┐ ┌────┴────┐
↓ ↓ ↓ ↓
[3,5] [2,4] [1,7] [8,6]
| | | |
┌─┴─┐ ┌─┴─┐ ┌─┴─┐ ┌─┴─┐
↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓
[3] [5] [2] [4] [1] [7] [8] [6]
=== 이제 병합 시작 (역순으로 올라감) ===
[3] [5] [2] [4] [1] [7] [8] [6]
└─┬─┘ └─┬─┘ └─┬─┘ └─┬─┘
↓ ↓ ↓ ↓
[3,5] [2,4] [1,7] [6,8]
└────┬────┘ └────┬────┘
↓ ↓
[2,3,4,5] [1,6,7,8]
└──────────────┬──────────────┘
↓
[1,2,3,4,5,6,7,8]
병합 과정 상세 설명
두 개의 정렬된 배열 `[2, 3, 4, 5]`와 `[1, 6, 7, 8]`을 병합하는 과정:
═══════════════════════════════════════════════════
초기 상태
═══════════════════════════════════════════════════
왼쪽 영역: [2, 3, 4, 5]
↑ leftAreaIndex
오른쪽 영역: [1, 6, 7, 8]
↑ rightAreaIndex
임시 배열: [0, 0, 0, 0, 0, 0, 0, 0]
↑ tempArrIndex
═══════════════════════════════════════════════════
비교 1: 2 vs 1
═══════════════════════════════════════════════════
2 > 1 → 1을 선택
tempArr: [1, 0, 0, 0, 0, 0, 0, 0]
↑
왼쪽: [2, 3, 4, 5] 오른쪽: [1, 6, 7, 8]
↑ ↑
═══════════════════════════════════════════════════
비교 2: 2 vs 6
═══════════════════════════════════════════════════
2 < 6 → 2를 선택
tempArr: [1, 2, 0, 0, 0, 0, 0, 0]
↑
왼쪽: [2, 3, 4, 5] 오른쪽: [1, 6, 7, 8]
↑ ↑
═══════════════════════════════════════════════════
비교 3: 3 vs 6
═══════════════════════════════════════════════════
3 < 6 → 3을 선택
tempArr: [1, 2, 3, 0, 0, 0, 0, 0]
↑
왼쪽: [2, 3, 4, 5] 오른쪽: [1, 6, 7, 8]
↑ ↑
═══════════════════════════════════════════════════
비교 4: 4 vs 6
═══════════════════════════════════════════════════
4 < 6 → 4를 선택
tempArr: [1, 2, 3, 4, 0, 0, 0, 0]
↑
왼쪽: [2, 3, 4, 5] 오른쪽: [1, 6, 7, 8]
↑ ↑
═══════════════════════════════════════════════════
비교 5: 5 vs 6
═══════════════════════════════════════════════════
5 < 6 → 5를 선택
tempArr: [1, 2, 3, 4, 5, 0, 0, 0]
↑
왼쪽: [2, 3, 4, 5] 오른쪽: [1, 6, 7, 8]
↑ (끝) ↑
═══════════════════════════════════════════════════
왼쪽 영역 모두 소진! 오른쪽 나머지를 복사
═══════════════════════════════════════════════════
오른쪽 남은 원소: [6, 7, 8]
→ 순서대로 tempArr에 복사
tempArr: [1, 2, 3, 4, 5, 6, 7, 8]
↑ ↑ ↑
복사된 원소들
최종 결과: [1, 2, 3, 4, 5, 6, 7, 8] ✓
Java 구현
public class MergeSort {
/**
* 병합 정렬 메인 함수
* @param arr 정렬할 배열
* @param leftIndex 정렬 범위의 시작 인덱스
* @param rightIndex 정렬 범위의 끝 인덱스
*/
public static void mergeSort(int[] arr, int leftIndex, int rightIndex) {
// 기저 조건: 원소가 1개 이하면 이미 정렬된 상태
if (leftIndex < rightIndex) {
// 중간 인덱스 계산
int midIndex = (leftIndex + rightIndex) / 2;
// 왼쪽 절반 재귀적으로 정렬
mergeSort(arr, leftIndex, midIndex);
// 오른쪽 절반 재귀적으로 정렬
mergeSort(arr, midIndex + 1, rightIndex);
// 정렬된 두 부분을 병합
merge(arr, leftIndex, midIndex, rightIndex);
}
}
/**
* 두 개의 정렬된 부분 배열을 하나로 병합
* @param arr 원본 배열
* @param leftIndex 왼쪽 부분의 시작 인덱스
* @param midIndex 왼쪽 부분의 끝 인덱스 (오른쪽 부분의 시작은 midIndex + 1)
* @param rightIndex 오른쪽 부분의 끝 인덱스
*/
private static void merge(int[] arr, int leftIndex, int midIndex, int rightIndex) {
// 왼쪽 영역의 시작 인덱스
int leftAreaIndex = leftIndex;
// 오른쪽 영역의 시작 인덱스
int rightAreaIndex = midIndex + 1;
// 임시 배열 생성 (병합 결과를 저장)
int[] tempArr = new int[rightIndex + 1];
// 임시 배열에 데이터를 삽입할 인덱스
int tempArrIndex = leftIndex;
// 두 영역을 비교하며 작은 값을 tempArr에 삽입
while (leftAreaIndex <= midIndex && rightAreaIndex <= rightIndex) {
if (arr[leftAreaIndex] <= arr[rightAreaIndex]) {
// 왼쪽 영역의 값이 작거나 같으면 왼쪽 선택
tempArr[tempArrIndex] = arr[leftAreaIndex];
leftAreaIndex++;
} else {
// 오른쪽 영역의 값이 작으면 오른쪽 선택
tempArr[tempArrIndex] = arr[rightAreaIndex];
rightAreaIndex++;
}
tempArrIndex++;
}
// 왼쪽 영역에 남은 원소가 있으면 모두 복사
if (leftAreaIndex > midIndex) {
// 왼쪽이 먼저 소진됨 → 오른쪽 나머지 복사
for (int i = rightAreaIndex; i <= rightIndex; i++) {
tempArr[tempArrIndex] = arr[i];
tempArrIndex++;
}
} else {
// 오른쪽이 먼저 소진됨 → 왼쪽 나머지 복사
for (int i = leftAreaIndex; i <= midIndex; i++) {
tempArr[tempArrIndex] = arr[i];
tempArrIndex++;
}
}
// 임시 배열의 내용을 원본 배열에 복사
for (int i = leftIndex; i <= rightIndex; i++) {
arr[i] = tempArr[i];
}
}
// 배열 출력 메서드
public static void printArray(int[] arr) {
System.out.print("[");
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i]);
if (i < arr.length - 1) {
System.out.print(", ");
}
}
System.out.println("]");
}
// 테스트 메인 메서드
public static void main(String[] args) {
System.out.println("=== 기본 병합 정렬 ===");
int[] arr1 = {3, 5, 2, 4, 1, 7, 8, 6};
System.out.println("정렬 전:");
printArray(arr1);
mergeSort(arr1, 0, arr1.length - 1);
System.out.println("정렬 후:");
printArray(arr1);
}
}
```
/*
실행 결과
=== 기본 병합 정렬 ===
정렬 전:
[3, 5, 2, 4, 1, 7, 8, 6]
정렬 후:
[1, 2, 3, 4, 5, 6, 7, 8]
*/
단계별 병합 정렬
→ mergeSort 호출: leftIndex=0, rightIndex=7
범위: [3, 5, 2, 4, 1, 7, 8, 6]
midIndex=3 (분할)
→ mergeSort 호출: leftIndex=0, rightIndex=3
범위: [3, 5, 2, 4]
midIndex=1 (분할)
→ mergeSort 호출: leftIndex=0, rightIndex=1
범위: [3, 5]
midIndex=0 (분할)
→ mergeSort 호출: leftIndex=0, rightIndex=0
범위: [3]
원소 1개 → 정렬 불필요 (기저 조건)
→ mergeSort 호출: leftIndex=1, rightIndex=1
범위: [5]
원소 1개 → 정렬 불필요
병합 시작: [0~0] + [1~1]
병합 결과: [3, 5]
→ mergeSort 호출: leftIndex=2, rightIndex=3
범위: [2, 4]
midIndex=2 (분할)
→ mergeSort 호출: leftIndex=2, rightIndex=2
범위: [2]
원소 1개 → 정렬 불필요
→ mergeSort 호출: leftIndex=3, rightIndex=3
범위: [4]
원소 1개 → 정렬 불필요
병합 시작: [2~2] + [3~3]
병합 결과: [2, 4]
병합 시작: [0~1] + [2~3]
병합 결과: [2, 3, 4, 5]
→ mergeSort 호출: leftIndex=4, rightIndex=7
범위: [1, 7, 8, 6]
midIndex=5 (분할)
→ mergeSort 호출: leftIndex=4, rightIndex=5
범위: [1, 7]
midIndex=4 (분할)
→ mergeSort 호출: leftIndex=4, rightIndex=4
범위: [1]
원소 1개 → 정렬 불필요
→ mergeSort 호출: leftIndex=5, rightIndex=5
범위: [7]
원소 1개 → 정렬 불필요
병합 시작: [4~4] + [5~5]
병합 결과: [1, 7]
→ mergeSort 호출: leftIndex=6, rightIndex=7
범위: [8, 6]
midIndex=6 (분할)
→ mergeSort 호출: leftIndex=6, rightIndex=6
범위: [8]
원소 1개 → 정렬 불필요
→ mergeSort 호출: leftIndex=7, rightIndex=7
범위: [6]
원소 1개 → 정렬 불필요
병합 시작: [6~6] + [7~7]
병합 결과: [6, 8]
병합 시작: [4~5] + [6~7]
병합 결과: [1, 6, 7, 8]
병합 시작: [0~3] + [4~7]
병합 결과: [1, 2, 3, 4, 5, 6, 7, 8]
호출 스택의 깊이별 동작
깊이 0 (최상위)
┌────────────────────────────────────┐
│ mergeSort([3,5,2,4,1,7,8,6], 0, 7) │
│ midIndex = 3 │
└────────────┬───────────────────────┘
│
┌────────┴────────┐
↓ ↓
깊이 1
┌──────────────┐ ┌──────────────┐
│ mergeSort │ │ mergeSort │
│ ([...], 0,3) │ │ ([...], 4,7) │
│ mid = 1 │ │ mid = 5 │
└──────┬───────┘ └──────┬───────┘
│ │
┌────┴────┐ ┌────┴────┐
↓ ↓ ↓ ↓
깊이 2
┌─────┐ ┌─────┐ ┌─────┐ ┌─────┐
│(0,1)│ │(2,3)│ │(4,5)│ │(6,7)│
└──┬──┘ └──┬──┘ └──┬──┘ └──┬──┘
│ │ │ │
┌─┴─┐ ┌─┴─┐ ┌─┴─┐ ┌─┴─┐
↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓
깊이 3 (기저 조건)
[3] [5] [2] [4] [1] [7] [8] [6]
✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓
이제 병합하며 스택에서 빠져나감
시간 복잡도
분할 단계
n개 원소를 절반씩 나누면 레벨 0: n개 (1그룹) 레벨 1: n/2개씩 (2그룹) 레벨 2: n/4개씩 (4그룹) 레벨 3: n/8개씩 (8그룹) 레벨 k: 1개씩 (n그룹) 레벨 수 = log₂n
병합 단계
각 레벨에서 - 모든 원소를 한 번씩 비교/이동 - 연산 횟수 = n 총 레벨 수: log₂n 각 레벨의 연산: n 전체 연산 = n × log₂n = O(n log n)
시각적 복잡도 분석
═══════════════════════════════════════════════════
레벨별 연산 횟수 (n = 8 예제)
═══════════════════════════════════════════════════
레벨 0: [1,2,3,4,5,6,7,8]
└───────┬───────┘
8번 비교/이동
레벨 1: [2,3,4,5] [1,6,7,8]
└──┬──┘ └──┬──┘
4번 + 4번 = 8번
레벨 2: [3,5] [2,4] [1,7] [6,8]
└─┬─┘ └─┬─┘ └─┬─┘ └─┬─┘
2 + 2 + 2 + 2 = 8번
레벨 3: [3][5][2][4][1][7][8][6]
0번 (기저 조건)
총 레벨 수: log₂8 = 3
각 레벨 연산: 8 = n
전체 연산: 3 × 8 = 24 = n log n
병합 정렬은 항상 O(n log n)을 보장한다
공간 복잡도
- O(n): 병합 시 임시 배열 필요
- O(log n): 재귀 호출 스택
장점
- 안정적인 O(n log n)성능: 최악의 경우에도 O(n log n)을 보장한다
- 안정 정렬: 동일한 값의 상대적 순서를 유지한다
- 예측 가능한 성능: 입력 데이터에 관계없이 일정한 성능을 보여준다
- 분할 정복의 교과서적 예제: 이해하기 좋은 알고리즘 구조이다
단점
- 추가 메모리 필요: O(n)의 공간 복잡도가 필요하다
- 구현이 복잡: 재귀와 병합 로직 이해가 필요하다
- 작은 데이터에는 오버헤드: 재귀 호출 비용이 발생한다
- 제자리 정렬 아님: 임시 배열이 필요하다
병합 졍렬은 분할 정복 전략을 사용하여 배열을 재귀적으로 절반씩 나누고, 다시 정렬하면서 병합하는 알고리즘으로 대용량 데이터 처리와 안정 정렬이 필요한 실전 환경에서 널리 사용되는 강력한 알고리즘이다