====== Merge sort ======
{{tag>sorting algorithms recursion}}
===== Description =====
Program implements merge sort algorithm.

**Source**:  Guide to Prolog Programming (on-line tutorial)
===== Download =====
Program source code: {{merge_sort.pl}}
===== Listing =====
<code prolog>
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).</code>
===== Comments =====