De ce contează?
Ai un teanc de 8 caiete de corectat și doi colegi care vor să te ajute. Cum împarți munca? Dacă le dai un caiet ție și 7 unei singure persoane, n-ai câștigat aproape nimic — tot 7 caiete rămân îngrămădite. Dar dacă tai teancul fix la mijloc, 4 și 4, fiecare jumătate se taie iar la mijloc, 2 și 2, apoi 1 și 1. După doar 3 tăieturi ai bucăți de câte un caiet. Asta e tot secretul împărțirii în divide et impera: nu rupi o foaie pe rând, ci înjumătățești.
Intuiția
Divide et impera rezolvă o problemă mare spărgând-o în subprobleme și combinând rezultatele. Pasul cel mai important este cum tai: dacă tai mereu la mijloc, fiecare bucată are jumătate din mărime, așa că ajungi la bucăți de mărime 1 în doar log2(n) tăieturi. Dacă tai prost — un element într-o parte, restul în cealaltă — cobori extrem de încet și pierzi tot avantajul.