분할 정복

큰 문제를 같은 모양의 작은 문제 여러 개로 나누고(분할), 작은 문제를 각각 풀고(정복), 그 답을 합쳐 큰 문제의 답을 만드는 방법이다. 작은 문제도 같은 방식으로 다시 나누므로 보통 [재귀](/term/recursion)로 구현한다. 병합 정렬은 배열을 반으로 나눠 각각 정렬한 뒤 두 정렬된 반쪽을 합친다.