merge_sort([],[]).
merge_sort([X],[X]).
merge_sort([H1,H2|T], S) :- split([H1,H2|T], L1, L2), 
                    merge_sort(L1, S1), 
                    merge_sort(L2, S2), 
                    merge(S1, S2, S).

split([],[],[]).
split([H|T], [H|U], V) :- split(T, V, U).


merge(L, [], L).
merge([], [H|T], [H|T]).
merge([H1|T1], [H2|T2], [H1|T]) :- H1 =< H2, merge(T1, [H2|T2], T).
merge([H1|T1], [H2|T2], [H2|T]) :- H2 < H1, merge([H1|T1], T2, T).