% merge(Xs_l, Xs_r, Xs): Xs = Xs_l U Xs_r where Xs is a sorted list
merge(Xs, [], Xs).
merge([], Xs, Xs).

merge(Xs_l, Xs_r, Xs) :-
	  Xs_l = [Hl|Xs_l_prime]
	, Xs_r = [Hr|Xs_r_prime]
	, (
		(Hl =< Hr)
			->(
				  merge(Xs_l_prime, Xs_r, Xs_prime)
				, Xs = [Hl|Xs_prime]
			)
			; (
				  merge(Xs_l, Xs_r_prime, Xs_prime)
				, Xs = [Hr|Xs_prime]
			)
	  )
	.

%split(X, X_l, X_r) X_l U X_r == X and -2 < |X_l| - |X_r| < 2
split([], [], []).
split([X], [], [X]).
split(X, X_l, X_r) :-
	  X = [H_l, H_r|Xprime]
	, split(Xprime, Xprime_l, Xprime_r)
	, X_l = [H_l|Xprime_l]
	, X_r = [H_r|Xprime_r]
	.

msort_4([], []).
msort_4([X], [X]).
msort_4(X, Xs) :-
	  split(X, X_l, X_r)
	, msort_4(X_l, Xs_l)
	, msort_4(X_r, Xs_r)
	, merge(Xs_l, Xs_r, Xs)
	, !.

