Sortare prin interclasare (merge sort)

Aceasta metoda de ordonare are la baza interclasarea a doi vectori: fiind dati doi vectori ordonati se obtine un al treilea vector ordonat care va contine elementele din cei doi vectori.

Sortarea prin interclasare utilizeaza metoda Divide et Impera:

-se imparte vectorul in secvente din ce in ce mai mici., astfel incat fiecare secventa sa fie ordonata la un moment dat si interclasata cu o alta secventa din vector corespunzatoare.

-practic interclasarea va incepe cand se ajunge la o secventa formata din doua elemente. Aceasta odata ordonata se va interclasa cu o alta corespunzatoare. Cele doua secvente vor alcatui in subsir ordonat din vector mai mare care la randul lui se va interclasa cu subsirul corespunzator samd.

Se dau doi vectori sortati 
Algoritm
Se parcurg simultan cei doi vectori pentru a se compara un element dintr-un vector cu un element din celălalt vector. Elementul cu valoarea mai mică (sau mai mare) este copiat în vectorul destinație și șters din vectorul sursă. Această operație continuă până când este epuizat unul dintre vectori. Celelalte elemente care au rămas se adaugă la sfârșitul vectorului destinație.
Variabile de memorie
-vectorii a,b și c; vectorii a și b sunt vectorii sursă iar vectorul c este vectorul destinație;
-lungimile logice ale vectorilor, n și m;
-indici pentru parcurgerea vectorilor: i - pentru vectorul a, j -  pentru vectorul b și k -  pentru vectorul c.
O solutie de implementare:
#include <iostream>
using namespace std;
int main()
{int a[100],b[100],c[200],m,n,i,j,k;
cout<<"m=";cin>>m;//se scrie si citeste vectorul a
for(i=0;i<m;i++)
{cout<<"a["<<i+1<<"]=";cin>>a[i];}
cout<<"n=";cin>>n;//se scrie si citeste vectorul b
for(i=0;i<n;i++)
{cout<<"b["<<i+1<<"]=";cin>>b[i];}

i=j=k=0;    //interclasare
while(i<m&&j<n)
if(a[i]<b[j])
    c[k++]=a[i++];
else
     c[k++]=b[j++];
if(i<m)
     for(j=i;j<m;j++)
  c[k++]=a[j];
    else
     for(i=j;i<n;i++)
       c[k++]=b[i];
       for(i=0;i<k;i++)
       cout<<c[i]<<" ";
}