
isort(L1,L2) :- insertsort([],L1,L2).

%
% insertsort(S1,R,S2) takes sorted S1, unsorted Rest, returns sorted S2
%
insertsort(L,[],L).
insertsort(L1,[H|T],L3) :- 
	insert(L1,H,L2),
	insertsort(L2,T,L3).

%
% insert(L1,E,L2) inserts element E in sorted list L1 returning L2
%
insert([],E,[E]).
insert([H|T],E,[H|L]) :- H < E, insert(T,E,L).
insert([H|T],E,[E|[H|T]]) :- H >= E.
