% isSorted(L) : checks if a list is sorted (non-descending)
% insertSort(N,L,R) : R is result of inserting N into sorted list L

% isSorted(L)
% ----------
% succeeds iff L is a list of values sorted in non-descending order (by @=<)
isSorted([]).
isSorted([N]).
isSorted([M,N|T]) :- M @=< N, isSorted([N|T]).

% insertSort(N,L,Result)
% ----------------------
% assuming L is a list of values sorted in non-descending order,
%    insertSort succeeds if Result is the list with N inserted
%    in its correct sorted position
% behaviour is undefined if original L is not sorted
insertSort(N, [], [N]).
insertSort(N, [H|T], [N,H|T]) :- N @< H.
insertSort(N, [H|T], [H|R]) :- insertSort(N, T, R).