|
|
— |
pl:prolog:pllib:merge_sort [2019/06/27 15:50] (aktualna) |
| ====== 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 ===== |
| |