%
%	Insertion Sort
%
procedure sort (var A: array 1..* of string, N:int)

    var inserted: boolean
    var next: string

    for s : 2..N			% A(1..s-1) are sorted
	next := A(s)
	inserted := false
	for decreasing pos: s..2	% find place to insert
	    if A(pos-1) <= next then
		A(pos)   := next
		inserted := true
		exit
	    else
		A(pos) := A(pos-1)	% shift element one down
	    end if
	end for

	if not inserted then
	    A(1) := next
	end if
    end for
end sort