% Referencias:
%   http://ktiml.mff.cuni.cz/~bartak/prolog/sorting.html
%   https://www.csupomona.edu/~jrfisher/www/prolog_tutorial/2_7.html
%   http://200.17.141.213/~gutanunes/hp/IA/prolog_palazzo.pdf
%   http://stackoverflow.com/questions/10063838/understanding-the-splitting-in-swi-prolog


%-------------------------
% ORDENACAO POR INTERCALACAO

merge_sort([],[]).     % empty list is already sorted
merge_sort([X],[X]).   % single element list is already sorted
merge_sort(List,Sorted) :-
    List=[_,_|_], divide(List,L1,L2),               % list with at least two elements is divided into two parts
	merge_sort(L1,Sorted1), merge_sort(L2,Sorted2), % then each part is sorted
	merge(Sorted1,Sorted2,Sorted).                  % and sorted parts are merged
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,L1,L2) :- halve(L,L1,L2).


halve(List,A,B) :- halve(List,List,A,B), !.
halve(B,[],[],B).
halve(B,[_],[],B).
halve([H|T],[_,_|T2],[H|A],B) :-halve(T,T2,A,B). 
