%összefűzéses rendezés
%Van egy lista, kettébontjuk, L1 és L2
%Rekurzív lépés:
%   L1 első eleme: X
%   L2 első eleme: Y
%   Ha X =< Y
%       X berak, L1 első eleme: M, L2 első eleme: Y
%   Ha X > Y
%       Y berak, ...
%Bemeneti lista: L
%Kimeneti lista: N
mergesort(L,N) :- split(L,O,E), mergesort(O, SO), mergesort(E,SE), merge(SO,SE,N).

%Bemeneti: SO, SE (listák)
%Kimeneti: N
%! --> több alternatívát ne nézzen
mergesort([], []) :- !.
mergesort([X], [X]) :- !.
merge(SO,SE,N) :- merge(SO,SE,[],N).
merge([X|SO],[Y|SE], A, N) :- X=<Y, merge(SO,[Y|SE],[X|A], N).
merge([X|SO],[Y|SE],A,N) :- X>Y, merge([X|SO], SE, [Y|A], N).
%Az SE-ben van egy olyan nagy elem, ami nagyobb, mint a többi
merge([], SE, A, N) :- reverse(A,B), append(B,SE,N).
merge(SO,[],A,N) :- merge([], SO, A, N).