% insert(Element, List)
% ---------------------
% insert an element into a sorted list

% inserting an element into an empty list gives a 1-element list
insert( E, [], [E]).

% handle the case where the new element belongs at the front
insert( E, [H|T], [E,H|T] )  :- E < H. 

% otherwise insert the new element into the tail
insert( E, [H|T], [H|R]) :-
   insert(E, T, R).


% insertList(Contents, Target, Result)
% ------------------------------------
% assuming the Target is sorted,
%    insert a the elements of L into it one at a time,
%    producing result

% no elements to insert
insertList([], Target, Target).

% general case: insert the front element first, 
%    then recursively insert the rest
insertList([H|T], Target, Result) :-
    insert(H, Target, Temp),
    insertList(T, Temp, Result).


% insertSort(List, Result)
% ------------------------
% perform insertionSort of a list by 
%    inserting each of its elements, one at a time
insertSort(L, Result) :- insertList(L, [], Result).