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
mymerge(Sorted1,Sorted2,Sorted). % and sorted parts are merged
mymerge([],L,L).
mymerge(L,[],L):-L\=[].
mymerge([X|T1],[Y|T2],[X|T]):-X=<Y,mymerge(T1,[Y|T2],T).
mymerge([X|T1],[Y|T2],[Y|T]):-X>Y,mymerge([X|T1],T2,T).
divide(L,L1,L2):-halve(L,L1,L2).
halve(L,A,B):-hv(L,[],A,B).
hv(L,L,[],L). % for lists of even length
hv(L,[_|L],[],L). % for lists of odd length
hv([H|T],Acc,[H|L],B):-hv(T,[_|Acc],L,B).