Sortare prin interclasare(mergesort) Tabloul unidimensional V se completeaza cu n numere reale. Sa se ordoneze crescator folosind sortare prin interclasare. Sortarea prin interclasare se bazeaza pe urmatoarea logica : vectorul V se imparte ,prin injumatatiri succesive ,in vectori din ce in ce mai mici ;cand se ating vectorii de maxim doua elemente ,fiecare dintre acestia se ordoneaza printr-o simpla comparare a elementelor ;cate doi astfel de mini- vectori ordonati se interclaseaza succesiv pana se ajunge iar la vectorul V. 39734mmu66nko3q program mergesort; type vector=array[1..50] of real ; var v:vector ;n,i:word; procedure schimba(li,ls:word;var a:vector); var man:real; begin if a[li]>a[ls] then begin man:=a[li]; a[li]:=a[ls]; a[ls]:=man; mk734m9366nkko end; end; procedure interclas(li,m,ls:word;var a:vector); var b:vector:i,k,p,j:word; begin i:=li; j:=m+1; k:=0; while (i<=m)and(j<=ls) do begin inc(k); if a[i] <a[j] then begin b[k]:=a[i]; inc(i); end else begin b[k]:=a[j]; inc(j); end; end; if i<=m then for p:=i to m do begin1 inc(k);b[k]:=a[p]; end; if j<=ls then for p:=j to ls do begin inc(k) ;b[k]:=a[p]; end; k:=0; for p:=li to ls do begin inc(k); a[p]:=b[k]; end; end; procedure divi(li,ls:word; var a:vector); var m:word; begin if (ls-li)<=1 then schimba(li,ls,a); else begin m:=(li+ls)div 2; divi(li,m,a); divi(m+1,ls,a); interclas(li,m,ls,a); end; end; begin write(‘cate elemente are vectorul?=’);readln(n); for i:=1 to n do begin write(‘tastati elementul’,i,’=’); readln(v[i]); end; divi(1,n,v); writeln(‘vectorul sortat este:’); for i:=1 to n do writeln(v[i]); end. OBSERVATII 4mecanismul general de tip Divide et Impera se gaseste implementat in procedura “divi” ; 4o astfel de abordare a problemei sortarii unii vector conduce la economie de timp de calcul ,deoarece operatia de interclasare a doi vectori deja ordonati este foarte rapida ,iar ordonarea independenta celor doua jumatati(mini- vectori) consuma in total aproximativ a doua parte din timpul care ar fi necesar ordonarii vectorului luat ca intreg .
