문제를 나누는 기준
입력의 크기를 줄이는 방식과 부분 문제의 결과에서 원래 답을 얻는 방법을 함께 정한다. 나누기만 하고 결과를 올바르게 연결할 수 없다면 원래 문제를 해결한 것이 아니다.
병합 정렬의 예
배열을 두 부분으로 나누고 각 부분을 정렬한 다음 두 정렬된 결과를 병합한다. 한 원소만 있는 배열은 이미 정렬되어 있으므로 직접 해결할 수 있는 기본 경우다. 이 기본 경우에서 재귀가 끝난다.
결합 비용
작은 문제를 여러 개로 나누는 비용뿐 아니라 결과를 합치는 비용도 전체 실행 시간에 들어간다. 병합 정렬에서는 각 단계의 병합이 전체 원소 수에 비례하고 분할 깊이가 로그 수준이어서 O(n log n)이 된다.
재귀와의 구별
재귀는 함수가 자신을 호출하는 표현 방식이고 분할 정복은 문제를 설계하는 전략이다. 모든 재귀가 분할 정복인 것은 아니다. 부분 문제가 많이 겹치는 경우에는 결과를 저장하는 동적 계획법이 중복 계산을 줄이는 데 유용할 수 있다.