% The merge of two sorted lists is the sorted riffle shuffle of the two.

% version 0 is cut free
merge(A, [], A).
merge([], B, B).
merge([A|RestAs], [B|RestBs], [A|Merged]):-
    A < B,
    merge(RestAs, [B|RestBs], Merged).
merge([A|RestAs], [B|RestBs], [B|Merged]):-
    B =< A,
    merge([A|RestAs], RestBs, Merged).

% version 1 has green cuts
merge1(A, [], A) :- !.
merge1([], B, B) :- !.
merge1([A|RestAs], [B|RestBs], [A|Merged]):-
    A < B, !,
    merge1(RestAs, [B|RestBs], Merged).
merge1([A|RestAs], [B|RestBs], [B|Merged]):-
    B =< A, !,
    merge1([A|RestAs], RestBs, Merged).

% version 2 has an if-then-else red cut:
merge2(A, [], A).
merge2([], B, B).
merge2([A|RestAs], [B|RestBs], [A|Merged]):-
    A < B, !,
    merge2(RestAs, [B|RestBs], Merged).
merge2([A|RestAs], [B|RestBs], [B|Merged]):-
    merge2([A|RestAs], RestBs, Merged).


% version 3 has a canned if-then-else cut using A -> B ; C
merge3(A, [], A).
merge3([], B, B).
merge3([A|RestAs], [B|RestBs], [C|Merged]):-
    A < B
    -> (merge3(RestAs, [B|RestBs], Merged), A=C)
    ;  (merge3([A|RestAs], RestBs, Merged), C=B).

% Mergesort splits a list into two sublists, recursively sorting,
% then merges the results.

mergesort([], []).
mergesort([A], [A]).
mergesort([A, B|Rest], Sorted):-
     split([A, B|Rest], L1, L2),
     mergesort(L1, Sorted1),
     mergesort(L2, Sorted2),
     merge(Sorted1, Sorted2, Sorted).

% Split by assigning alternate elements to  the sublists (non-optimal)
split([], [], []).
split([A], [A], []).
split([A, B|Rest], [A| RestA], [B|RestB]):-
     split(Rest, RestA, RestB).


%| ?- ['mergesort'].
%% consulting /amd/nfs/roc/disk/ptn013/aiugrad.97/markc/LCTG/mergesort...
%% consulted /amd/nfs/roc/disk/ptn013/aiugrad.97/markc/LCTG/mergesort in module user, 0 msec 3464 bytes
%yes
%| ?- mergesort([3,1,4,2], [1,2,3,4]).
%yes
%| ?- mergesort([3,1,4,2], Sorted).
%Sorted = [1,2,3,4] ?
%yes
%| ?- mergesort([3,1,4,2], Sorted).
%Sorted = [1,2,3,4] ? ;
%no
%| ?- mergesort(Shuffled, [1,2,3,4]).
%! Instantiation error in argument 2 of < /2
%! goal:  1<_80
%| ?-

% The < operator (and any other relation operator) acts
% as if it contained a tacit cut.
% Thus the instantiation fails because the cut is attempting to 
% commit to the instantiation of an uninstantiated variable.

% This is one of several operators which are "impure" prolog.
% Another notable impure operator is the "is" operator used
% to force evaluation of arithmetic expresion.