sort([], []).
sort([X],[X]).
sort(Seq, Srt) :- split(Seq, A, B),
                  sort(A, SA),
                  sort(B, SB),
                  merge(SA, SB, Srt).

split([], [], []).
split([X], [X], []).
split([X|[Y|Seq]], [X|A], [Y|B]) :- split(Seq, A, B).

merge([], [], []).
merge(X, [], X).
merge([], Y, Y).
merge([X|SA], [Y|SB], [X|Srt]) :- order(X, Y),
                                  merge(SA, [Y|SB], Srt).
merge([X|SA], [Y|SB], [Y|Srt]) :- merge([X|SA], SB, Srt).

order(X, Y) :- X @< Y.