Divide and Conquer

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));
}

References

• ↗ https://en.wikipedia.org/wiki/Divide-and-conquer_algorithm

Tags

Related Terms