4
1
|
3
2
작은 문제도 “정렬 배열 반환”이라는 같은 형태다.
분할 정복의 계약은 추상 문장보다, 입력이 분해되고 다시 같은 의미의 반환값으로 합쳐지는 과정을 봐야 고정된다.
작은 문제도 “정렬 배열 반환”이라는 같은 형태다.
길이 1은 이미 정렬된 배열로 즉시 반환된다.
하위 반환값이 이미 정렬되어 있다는 계약을 이용한다.
상위 호출도 같은 계약, 정렬 배열 반환을 만족한다.
| 질문 | 이 입력에서 확인한 답 | 빠지면 생기는 문제 |
|---|---|---|
| 작은 문제도 같은 형태인가 | 왼쪽/오른쪽 모두 정렬 배열을 반환한다. | 하위 호출 반환값의 의미가 달라진다. |
| 기저는 계약을 만족하나 | 길이 1 배열은 이미 정렬되어 있다. | 재귀가 멈춰도 답이 아닐 수 있다. |
| 병합이 계약을 보존하나 | 두 정렬 배열을 비교해 전체 정렬 배열을 만든다. | 중앙 교차나 잔여 구간이 누락된다. |