De ce contează?
Ai două teancuri de cărți, fiecare deja sortat crescător, cu fața în sus. Vrei un singur teanc sortat. Cum procedezi cel mai rapid? Te uiți doar la cartea de deasupra fiecărui teanc, o iei pe cea mai mică, o pui în teancul final — și repeți. Nu reamesteci nimic: te folosești de faptul că fiecare teanc e deja ordonat. Exact asta face pasul „combină” din divide-et-impera.
Intuiția
Divide-et-impera are trei pași: împarți problema în jumătăți, rezolvi recursiv fiecare jumătate, apoi combini rezultatele. Primii doi pași sunt ușor de imaginat; al treilea decide cât de rapid e algoritmul.
La merge sort, „combină” înseamnă interclasare (merge): ai două jumătăți deja sortate și trebuie să le lipești într-un singur vector sortat. Truc-ul e că nu pornești de la zero — capetele celor două jumătăți îți spun mereu care e următorul cel mai mic element.