The merge-sort algorithm divides a vector into two vectors, sorts them and intersperses them. If the resulted vectors have more than one element, then the same method is applied to each of them and so on.

Pascal Program:

type vector=array[1..100] of integer;

var a:vector;

i,j,k,l,m,n:integer;

procedure sort(li,ls:integer);

var aux:integer;

begin

if a[li]>a[ls] then

begin

aux:=a[li];

a[li]:=a[ls];

a[ls]:=aux;

end;

end;

procedure interclasare(li,ls,m:integer);

var b:vector; k,i,j:integer;

begin

fillchar(b,sizeof(b),0);

i:=li;

j:=m+1;

k:=0;

while (i<=m) and (j<=ls) do

if a[i]<a[j] then

begin

inc(k);

b[k]:=a[i];

inc(i);

end

else

begin

inc(k);

b[k]:=a[j];

j:=j+1;

end;

if i<=m then

begin

for j:=i to m do

begin

inc(k);

b[k]:=a[j];

end;

end

else

begin

for i:=j to ls do

begin

inc(k);

b[k]:=a[i];

end;

end;

k:=0;

for i:=li to ls do

begin inc(k);

a[i]:=b[k];

end;

end;

procedure divide(li,ls:integer);

var m:integer;

begin

if ls-li<=1 then sort(li,ls)

else

begin

m:=(li+ls) div 2;

divide(li,m);

divide(m+1,ls);

interclasare(li,ls,m);

end;

end;

begin

for i:=1 to n do

divide(1,n);

for i:=1 to n do

write(a[i],' ');

writeln;

end.

C++ Program:

#include<iostream.h>

int a[100],i,j,k,l,m,n;

void sort(int li,int ls)

{

int aux;

if (a[li]>a[ls]) { aux=a[li]; a[li]=a[ls]; a[ls]=aux; }

}

void interclas(int li, int ls, int m)

{

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

i=li;

j=m+1;

k=0;

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

{

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

else {k+=1; b[k]=a[j]; j+=1;}

}

if (i>=m)

{

for (j=i;j<=m;j++)

{

k+=1;

b[k]=a[j];

}

}

else

{

for(i=j;i<=ls;i++)

{

k+=1;

b[k]=a[i];

}

}

k=0;

for (i=li;i<=ls;i++)

{

k+=1;

a[i]=b[k];

}

}

void divide(int li, int ls)

{

int m;

if (ls-li<=1)

{sort(li,ls);}

else

{

m=(li+ls)/2;

divide(li,m);

divide(m+1,ls);

interclas(li,ls,m);

}

}

void main()

{

cin>>n;

for (i=1;i<=n;i++)

cin>>a[i];

divide(1,n);

for (i=1;i<=n;i++)

cout<<a[i]<<" ";

cout<<endl;

}

This sorting method uses Divide et Impera and recursivity.