Divide and conquer
Algoritm-strategi: dela problemet i mindre delproblem, lös dem rekursivt, kombinera lösningarna. "Splittra och härska".
Klassiska exempel: merge sort (dela arrayen, sortera halvorna, merge), quick sort (välj pivot, partitionera, sortera båda sidor), binary search, FFT, Karatsuba multiplication, Strassen's matrix multiplication. Master Theorem ger tidskomplexiteten för rekursionsrelationen.
Naturligt parallelliserbart — varje rekursion oberoende. MapReduce och Hadoop är industriell divide-and-conquer på data. Trade-off: rekursions-overhead i botten av rekursionen; ofta byter man till insertion sort vid små subarrays.