% merge(+OrderedList1,+OrderedList2,-OrderedUnion)
merge([],V,V).
merge(V,[],V).
merge([H1|T1],[H2|T2],[H1|V]) :- H1<H2,
    merge(T1,[H2|T2],V).
merge([H1|T1],[H2|T2],[H2|V]) :- H1>=H2,
    merge([H1|T1],T2,V).

% split(?ListOfItems,?ListOfSingletonListsWithItems)
split([],[]).
split([H1|T1],[[H1]|V]):- split(T1,V).

% mergelist(+Lists,-PairwiseMergedLists)
mergelist([],[]).
mergelist([X],[X]).
mergelist([X,Y|Z],[V|Z1]) :- merge(X,Y,V),
    mergelist(Z,Z1).

% mergelists(+Lists,-PairwiseMergedListsToOneList)
mergelists([],[]).
mergelists([X], [X]) :- !.
mergelists(L,V) :-
    mergelist(L, L1),
    mergelists(L1, V).

% mergesort(+List,-SortedList)
mergesort(L,R):-split(L,L1),mergelists(L1,[R]).

% quicksort(+List,-SortedList)
quicksort([],[]).
quicksort([X],[X]) :- !.
quicksort([X,Y],[X,Y]):-X<Y,!.
quicksort([X,Y],[Y,X]):-X>=Y,!.
quicksort([H|T],R):-
   partition(H,T,M,V),
   quicksort(M,M1),
   quicksort(V,V1),
   append(M1,[H|V1],R).

% partition(+Pivot,+List,-LessThanList,-GreaterOrEqualList)
partition(_,[],[],[]).
partition(P,[H|T],[H|M],V) :-
    H<P,
    partition(P,T,M,V).
partition(P,[H|T],M,[H|V]) :-
    H>=P,
    partition(P,T,M,V).

% heads(+ListOfLists,-FirstItems)
heads([],[]).
heads([[H|_]|T], [H|V]) :-
    heads(T, V).
% heads(+ListOfLists,-TailsOfLists)
tails([],[]).
tails([[_|T1]|T], [T1|V]) :-
    tails(T,V).

% emptys(EmptyLists)
emptys([]).
emptys([[]|T]) :- emptys(T).

% transpose(+RowMatrix,-ColMatrix)
transpose(L,[]) :- emptys(L).
transpose(L,[S1|T1]) :-
    heads(L,S1),
    tails(L,Ts),
    transpose(Ts, T1).

% reverse(+List,-ReversedList)
reverse([],[]).
reverse([H|T], V) :-
    reverse(T, V1),
    append(V1, [H], V).

% reverseA(+List,-ReversedListWithTail,+Tail)
reverseA([],A,A).
reverseA([H|T],V,A):- reverseA(T,V,[H|A]).

% norm2diff(+NormalList,-DifferenceList)
norm2diff([], A - A).
norm2diff([H|T],[H|L2]-A) :-
    norm2diff(T,L2-A).

% norm2diff(+DifferenceList,-NormalList)
diff2norm(L-[],L).

% appendDiff(+DifferenceList,+DifferenceList,-AppendedDiffList)
% originally: appendMiruv
appendDiff(A-B,B-C,A-C).

% printlist(+DiffListToPrintOut)
printlist(X-X):-var(X).
printlist([H|T]-X):- \+ var(H),writeln(H),printlist(T-X).