Let i be a number with the property a[1]<=a[2]<=.......<=a[i-1]. The strategy is to insert a[i+1] in the first (ordered) part of the array. This operation implies moving a sequence to the right.

Pascal Program:

var a:array[1..100] of integer;

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

procedure sort;

begin

for i:=2 to n do

begin

j:=1;

while (j<i) and (a[j]<a[i]) do

inc(j);

k:=a[i];

for l:=i-1 downto j do

a[l+1]:=a[l];

a[j]:=k;

end;

end;

begin

readln(n);

for i:=1 to n do

readln(a[i]);

sort;

for i:=1 to n do

write(a[i],' ');

end.

C++ Program:

#include <iostream.h>

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

void sort()

{

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

{

j=1;

while ((j<i)&(a[j]<a[i]))

j=j+1;

k=a[i];

for (l=i-1;l>=j;l--)

a[l+1]=a[l];

a[j]=k;

}

}

void main()

{

cin>>n;

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

cin>>a[i];

sort();

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

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

cout<<endl;

}

Time: O(n^2)