Divide and conquer

The method defines smaller instances of the same problem, solves them recursively, and combines their answers. Small base cases terminate the recursion. A recursive call that never reduces the instance does not make progress merely because the code is recursive.

Merge sort illustrates the structure: sort two halves and merge them with a linear scan. Each child promises an ordered region, while merging converts those local guarantees into an ordered whole. Both the subproblem contract and combination rule matter to correctness.

References: [1]

Two equal subproblems plus linear combination give a recurrence such as T(n)=2T(n/2)+O(n). Under unit-cost comparisons, O(n) total work per logarithmic level yields O(n log n) for merge sort.

Quicksort also recursively handles two regions, but their sizes depend on the partition. Repeatedly unbalanced partitions produce a different recurrence. Divide and conquer does not automatically guarantee logarithmic depth; the actual division rule must justify it.

References: [1] [2]

Independent subproblems can be handled separately, but different branches may repeatedly create the same state. Naive Fibonacci recursion recomputes identical indexes; dynamic programming changes that cost through reuse.

Division, copying, combination and call state also consume resources. Array merging uses auxiliary storage, and separately describable tasks still incur communication and scheduling overhead if parallelized. The design structure alone does not establish a performance gain.

References: [3] [1]