Williams' insertion algorithm

/* Sort A[1..N] using Binary Insertion Soft */
for 1 := 2 to N do
begin
/* Invariant: A[1..I-1] is sorted */
L := 1; R:= I-1;
T := A[1];
/* binary search for the insert */
/* position of T within A[1..I-1] */
While L <= R do
begin
M := (L + R) DIV 2;
if T < A[M] then R := M-1
else L := M+1;
end;
/* sift down to position L */
for J := I-1 down to L do A[J+1] := A[J];
/* insert into proper position */
A[L] := T;
end;