Divide and Conquer
debt(d7/e5/b3/t5)
Closest to 'only careful code review or runtime testing' (d7). The term's detection_hints explicitly state automated detection is 'no'. Recognizing that an O(n²) problem could be solved with divide and conquer requires manual code review or performance testing — no linter or SAST tool will flag 'you could use mergesort here instead of bubble sort'.
Closest to 'touches multiple files / significant refactor in one component' (e5). The quick_fix describes a paradigm shift in algorithm design. Converting a naive O(n²) iterative solution to a divide-and-conquer recursive solution requires restructuring the algorithm logic, adding base cases, implementing the combine step, and potentially adding helper functions — a significant refactor within the component.
Closest to 'localised tax' (b3). Applies_to shows web/cli contexts, but divide and conquer is typically applied to specific algorithmic problems rather than system-wide architecture. Once implemented correctly, a D&C algorithm is self-contained — other parts of the codebase don't need to understand the paradigm, they just call the function.
Closest to 'notable trap' (t5). The misconception field explicitly states developers think 'divide and conquer is only useful for sorting' when it actually applies broadly to matrix multiplication, closest pair, MapReduce, etc. Common_mistakes lists several gotchas: missing base case causing infinite recursion, unbalanced division degrading to O(n²), forgetting the combine step. These are documented pitfalls most developers learn through experience.
Also Known As
TL;DR
Explanation
Divide and conquer has three steps: divide (split into subproblems), conquer (solve recursively, base case for small inputs), combine (merge solutions). The Master Theorem analyses recurrences of the form T(n) = aT(n/b) + f(n). Mergesort: divide array in half, sort each half, merge — O(n log n). Quicksort: partition around pivot, sort partitions — O(n log n) average, O(n²) worst. Fast Fourier Transform: O(n log n) polynomial multiplication using complex roots of unity. In PHP: usort() uses an optimised comparison sort; for custom divide-and-conquer use recursion with array_slice().
Diagram
flowchart TD
ARR[Array: 8 3 1 5 2 7 4 6] --> SPLIT[Divide in half]
SPLIT --> L[8 3 1 5]
SPLIT --> R[2 7 4 6]
L --> LL[8 3] & LR[1 5]
R --> RL[2 7] & RR[4 6]
LL --> LL1[8] & LL2[3]
LL1 & LL2 -->|merge sorted| LLM[3 8]
LR -->|merge| LRM[1 5]
LLM & LRM -->|merge| LM[1 3 5 8]
RL -->|merge| RLM[2 7]
RR -->|merge| RRM[4 6]
RLM & RRM -->|merge| RM[2 4 6 7]
LM & RM -->|final merge| SORTED[1 2 3 4 5 6 7 8]
style SORTED fill:#238636,color:#fff
style ARR fill:#6e40c9,color:#fff
Common Misconception
Why It Matters
Common Mistakes
- No base case — recursive divide without a termination condition causes infinite recursion.
- Unbalanced division — always dividing 1 vs n-1 degrades to O(n²) like naive quicksort on sorted input.
- Forgetting the combine step — solutions to subproblems must be merged into the final answer.
- Stack overflow for deep recursion — PHP has limited stack depth; use explicit stack for very deep recursion.
Code Examples
// O(n²) merge — combine step undoes the O(n log n) benefit:
function mergesort(array $arr): array {
if (count($arr) <= 1) return $arr;
$mid = intdiv(count($arr), 2);
$left = mergesort(array_slice($arr, 0, $mid));
$right = mergesort(array_slice($arr, $mid));
return array_merge($left, $right); // Wrong: not merging sorted arrays!
// array_merge just concatenates — unsorted result
}// Correct mergesort with O(n) merge step:
function mergesort(array $arr): array {
if (count($arr) <= 1) return $arr;
$mid = intdiv(count($arr), 2);
$left = mergesort(array_slice($arr, 0, $mid));
$right = mergesort(array_slice($arr, $mid));
return merge($left, $right); // O(n) sorted merge
}
function merge(array $l, array $r): array {
$result = []; $i = $j = 0;
while ($i < count($l) && $j < count($r)) {
$result[] = $l[$i] <= $r[$j] ? $l[$i++] : $r[$j++];
}
return array_merge($result, array_slice($l, $i), array_slice($r, $j));
}