SORTAREA PRIN INTERCLASARE - MERGE SORT

Acest algoritmul de sortare prin interclasare se bazează pe următoarea idee: pentru a sorta un vector cu n elemente îl împăţim în doi vectori care, odată sortaţi, se interclasează.

Conform strategiei Divide et Impera, problema este descompusă în alte două subprobleme de acelaşi tip şi, după rezolvarea lor, rezultatele se combină (în particular se interclasează). Descompunerea unui vector în alţi doi vectori care urmează a fi sortaţi are loc până când avem de sortat vectori de una sau două componente.

Exemplu Sortarea unui şir de şapte valori de tip întreg.

Algoritm descris în pseudocod:

Sort(p,q,A);

dacă A[p]>A[q] atunci

interschimba A[p]↔A[q]

sfSort

Interc(p,q,m,A)

i←p;j←m+1;k←0;

cât timp i<=m si j<=q execută

dacă A[i]<A[j] atunci

k←k+1;B[k] ←A[i];i←i+1

altfel

k←k+1;B[k] ←A[j];j←j+1;

sfdacă

sfcât timp

cât timp i<=m execută

k←k+1 B[k] ←A[i] i←i+1

sfcât timp

cât timp j<=q execută

k←k+1 B[k] ←A[j];j←j+1

sfcât timp

pentru i←p,q execută

A[i] ←B[i]

Sfpentru

Divimp(p,q,A)

dacă q-p<=1 atunci Sort(p,q,A)

altfel Divimp(p,m,A) Divimp(m+1,q,A)

Interc(p,q,m,A)

sfdacă

sfDivimp

Implementare în C++

void sort (int p,int q, int a[100] )

{ int m;

if (a[p]>a[q])

{m=a[p];a[p]=a[q];a[q]=m;}

}

void interc (int p,int q, int m, int a[100])

{

int b[100],i,j,k;

i=p; j=m+1; k=0;

while ((i<=m) && (j<=q))

if (a[i]<=a[j]) b[++k]=a[i++];

else b[++k]=a[j++];

while(i<=m)

b[++k]=a[i++];

while(j<=q)

b[++k]=a[j++];

for(i=p;i<=q;i++)

a[i]=b[i];

}

void divimp (int p, int q, int a[100])

{

int m;

if ((q-p)<=1) sort (p,q,a);

else

{ m=(p+q)/2;

divimp(p,m,a);

divimp(m+1,q,a);

interc(p,q,m,a);

}

}