% merge two sorted lists (assuming non-decreasing order)

% merge any list L with an empty list and we just get L
merge(L, [], L).
merge([], L, L).

% handle the case where the front of the first list
%    should be the front of the result
merge([H1|T1], [H2|T2], [H1|R]) :-
   H1 =< H2, 
   merge(T1, [H2|T2], R).

% otherwise the front of the second list
%    should be the front of the result
merge([H1|T1], [H2|T2], [H2|R]) :-
   merge([H1|T1], T2, R).