De ce contează?
Ai două teancuri de fișe, fiecare deja ordonat alfabetic. Vrei un singur teanc ordonat. Nu reordonezi totul de la capăt: te uiți doar la fișa de deasupra fiecărui teanc, o iei pe cea care vine prima în alfabet și o pui în teancul nou. Repeți. Pentru că fiecare teanc era deja ordonat, prima fișă bună e mereu una dintre cele două de deasupra — nu trebuie să cauți mai jos.
Intuiția
Interclasarea ia doi vectori deja sortați și îi combină într-unul singur, tot sortat. Cheia: dacă ambii sunt sortați crescător, cel mai mic element rămas e mereu la începutul unuia dintre ei. Așa că ții câte un deget pe capul fiecărui vector, compari cele două valori și o iei pe cea mai mică. Mută degetul, repetă. Aceasta este și inima algoritmului Merge Sort.
Tot algoritmul se reduce la o singură decizie repetată: compari cele două
fronturi (elementul de sub i și cel de sub j) și iei minimul. Pentru că
ambii vectori sunt sortați, minimul dintre cele două capete este garantat cel mai
mic element nepus încă — nu trebuie să te uiți mai adânc.