Interclasarea a doi vectori sortați

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]$

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)$.

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.

#include <iostream>
using namespace std;

int main() {
    int n, m, a[100], b[100], c[200];
    cin >> n >> m;
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = 0; i < m; i++) cin >> b[i];

    int i = 0, j = 0, k = 0;
    while (i < n && j < m) {
        if (a[i] <= b[j]) c[k++] = a[i++];
        else c[k++] = b[j++];
    }
    while (i < n) c[k++] = a[i++];
    while (j < m) c[k++] = b[j++];

    for (int t = 0; t < k; t++) cout << c[t] << " ";
    return 0;
}