This algorithm is used for sorting numbers in small intervals. Let A be the vector that needs sorting, n its length, and [a..b] the interval the elements of the vector are in. A vector B with b-a+1 elements is being built. On the position i of a the vector B we keep the number of times that the number a+i appears in vector A.

Pascal program:

var a:array[0..255] of integer;
b:array[0..255] of 0..1;
m1,m2,i,j,k,l,m,n:integer;

begin
readln(n);
m1:=maxint;
m2:=-maxint;
for i:=1 to n do
begin
readln(a[i]);
if a[i]<m1 then m1:=a[i];
if a[i]>m2 then m2:=a[i];
end;
for i:=1 to n do
inc(b[a[i]-m1]);
for i:=0 to m2-m1+1 do
for j:=1 to b[i] do
write(i+m1,' ');
writeln;
end.

 

C++ program:

#include<iostream.h>
void main()
{
int a[255],b[255],i,j,k,l,m1,m2,n;
cin>>n;
if (n>0){cin>>a[1];}
m1=a[1];
m2=a[1];
for(i=2;i<=n;i++)
{
cin>>a[i];
if (a[i]>m2){m2=a[i];}
if (a[i]<m1){m1=a[i];}
}
for (i=0;i<=255;i++)
b[i]=0;
for (i=0;i<=n;i++)
b[a[i]-m1]+=1;
for (i=0;i<=m2-m1+1;i++)
for (j=1;j<=b[i];j++)
cout<<i+m1<<" ";
cout<<endl;
}