Program implements merge sort algorithm.

Source: Guide to Prolog Programming (on-line tutorial)

Program source code: merge_sort.pl

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).