# Mergesort in prolog from http://kti.ms.mff.cuni.cz/~bartak/prolog/sorting.html


merge_sort([],[]).
    
merge_sort([X],[X]).   

merge_sort(List,Sorted):- List=[_,_|_], divide(List,L1,L2), merge_sort(L1,Sorted1),merge_sort(L2,Sorted2), merge(Sorted1,Sorted2,Sorted).                  

merge([],L,L).
    
merge(L,[],L):-L\=[].

merge([X|T1],[Y|T2],[X|T]):-X=<Y,merge(T1,[Y|T2],T).

merge([X|T1],[Y|T2],[Y|T]):-X>Y,merge([X|T1],T2,T).


divide(L,A,B):-hv(L,[],A,B).
 
hv(L,L,[],L).      

hv(L,[_|L],[],L).  

hv([H|T],Acc,[H|L],B):- hv(T,[_|Acc],L,B).
