shuffle(L, [], L).
shuffle(L, [E|Rrest], S) :-
    conc(L1, Lrest, L),
    shuffle(Lrest, Rrest, Srest),
    conc(L1, [E|Srest], S).

split([], [], []).
split([A], [A], []).
split([A,B|Rest], [A|RestA], [B|RestB]) :-
    split(Rest, RestA, RestB).

%redundant on empty string

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).

% mutually exclusive 

mergesort([], []).
mergesort([A], [A]).
mergesort(List, Sorted) :-
    splittable(List),
    split(List, A, B),
    mergesort(A, SortedA),
    mergesort(B, SortedB),
    merge(SortedA, SortedB, Sorted).

splittable([_First,_Second|_Rest]).

% mutually exclusive

max([Val], Val).
max([Val|Rest], RestMax) :- 
    max(Rest, RestMax),
    Val =< RestMax.
max([Val|Rest], Val) :- 
    max(Rest, RestMax),
    Val > RestMax.