# Interclasarea a doi vectori sortați

> Pagina: https://bacalaurescu.ro/informatica/lectii/algoritmi-clasici-bac/interclasare
> Markdown: https://bacalaurescu.ro/informatica/lectii/algoritmi-clasici-bac/interclasare.md
> Sursa: Bacalaurescu (bacalaurescu.ro), conținut gratuit pentru BAC 2027.

Materia: [Informatică](https://bacalaurescu.ro/informatica)

Capitolul: [Algoritmi clasici de BAC](https://bacalaurescu.ro/informatica/lectii/algoritmi-clasici-bac)
Actualizat: 2026-09-22

Algoritmul cu doi indici, complexitatea liniară și legătura cu sortarea prin interclasare.

## Problema

Ai doi vectori **deja sortați** crescător. Trebuie să obții un al treilea vector, tot sortat, care conține toate elementele.

## De ce nu concatenezi și sortezi

Ar merge, dar ai pierde informația că vectorii erau deja sortați. Concatenare plus sortare înseamnă $O((n+m) \log(n+m))$. Interclasarea corectă face **$O(n + m)$**, adică liniar.

## Algoritmul

Folosești **doi indici**, câte unul pentru fiecare vector:

1. cât timp ambii indici sunt în interiorul vectorilor, compari elementele curente și îl iei pe cel mai mic, avansând indicele corespunzător;
2. când unul dintre vectori s-a terminat, **copiezi restul celuilalt**, care e deja sortat.

Pasul 2 e esențial și e cel mai des uitat.

## Exemplu

$a = [1, 4, 7]$, $b = [2, 3, 8, 9]$

| Pas | Compară | Ia | Rezultat |
|---|---|---|---|
| 1 | 1 vs 2 | 1 | [1] |
| 2 | 4 vs 2 | 2 | [1,2] |
| 3 | 4 vs 3 | 3 | [1,2,3] |
| 4 | 4 vs 8 | 4 | [1,2,3,4] |
| 5 | 7 vs 8 | 7 | [1,2,3,4,7] |
| 6 | a epuizat | rest din b | [1,2,3,4,7,8,9] |

## Legătura cu sortarea prin interclasare

Interclasarea e pasul de bază al algoritmului **merge sort**: împarți vectorul în două, sortezi fiecare jumătate, apoi le interclasezi. Complexitate totală: $O(n \log n)$.

> [!RETINE]
> Cele **două bucle finale**, care copiază ce a rămas, nu sunt opționale. Fără ele pierzi elemente, iar programul dă rezultat parțial, care pare corect la prima vedere.

## Greșeli frecvente

1. Se uită copierea restului. Verifică mereu cu un exemplu în care un vector se termină primul.
2. Se folosește un singur indice pentru ambii vectori.
3. Se presupune că vectorii sunt sortați fără să fie. Interclasarea **cere** vectori sortați.