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
readln(n);
for i:=1 to n do
readln(a[i]);
divide(1,n);
for i:=1 to n do
write(a[i],' ');
writeln;
readln
end.
C++ Program:
#include<iostream.h>
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.
