%%% merge-sort algorithm
%%%%%%%%%%%%%%%%%%%%%%%%%%
% split list  -- recursive
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
my_split([],[],[]).
my_split([X],[X],[]):-!.
my_split([H1,H2|T],[H1|T2],[H2|T3]):-my_split(T,T2,T3).

% ?- my_split([1,5,4,2,10],L1,L2).
% L1=[1,4,10], L2=[5,2]

% split list with acc
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
my_split2(List,L1,L2):-my_splitAcc(List,[],[],L1,L2).
my_splitAcc([],Acc1,Acc2,Acc1,Acc2).
my_splitAcc([H1],Acc1,Acc2,L1,L2):-add_to_end(H1,Acc1,NewAcc1), my_splitAcc([],NewAcc1,Acc2,L1,L2),!.
my_splitAcc([H1,H2|T],Acc1,Acc2,L1,L2):-add_to_end(H1,Acc1,NewAcc1), add_to_end(H2,Acc2,NewAcc2), 
					my_splitAcc(T,NewAcc1,NewAcc2,L1,L2).

% ?- my_split2([1,5,4,2,10],L1,L2).
% L1=[1,4,10], L2=[5,2]

%%% add an element at the end of a list
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% add_to_end(Element,List,Res). 3, [4,5,6] ---> [4,5,6,3]

add_to_end(El,[],[El]):-!.
add_to_end(El,[H|T],[H|T2]):-add_to_end(El,T,T2).

% ?-add_to_end(3,[1,2,3,4,5],X).
% ?-add_to_end(4,[3],X).

% merge
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
merge1([],L2,L2):-!.
merge1(L1,[],L1):-!.
merge1([H1|T1],[H2|T2],[H1|T3]):-H1=<H2,!,merge1(T1,[H2|T2],T3).
merge1([H1|T1],[H2|T2],[H2|T3]):-H2<H1,merge1([H1|T1],T2,T3).

% ?-merge1([1,2,4,5,6],[2,3,4,10],X).
% X=[1,2,2,3,4,4,5,6,10]

% merge with acc
%%%%%%%%%%%%%%%%%%%%%5

merge2(L1,L2,Res):-mergeAcc(L1,L2,[],Res).
mergeAcc([],L1,Acc,[L1,Acc]).
mergeAcc(,[],Acc,Acc).

% ?-merge2([1,2,4,5,6],[2,3,4,10],X).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% mergesort
mergesort1([],[]).
mergesort1([X],[X]):-!.
mergesort1([H|T],Res):-my_split([H|T],L1,L2),mergesort1(L1,S1),
			mergesort1(L2,S2),merge1(S1,S2,Res).

% ?-mergesort1([4,2,1,9,-10,4,3],X).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% generate random lists

% generate_elem_list(Len,Interval,Result).

generate_elem_list(Len,Interval,Result):-genAcc(Len,Interval,[],Result).
genAcc(0,_,Acc,Acc):-!.
genAcc(Len,Interval,Acc,Result):-Len>0, Len1 is Len-1, H is random(Interval),
				genAcc(Len1,Interval,[H|Acc],Result).

% ?-generate_elem_list(10,2,X).
% X=[0,0,0,1,1,0,1,0,0,1]

% ?-generate_elem_list(4,11,X).
% X=[5,10,0,2]