% Merge Sort, corrigido!!
%             e com cuts para que nao de mais de uma solucao
%

mergesort([],[]) :-!.
mergesort([X],[X]) :-!.   % <---  corrigido (somado)
mergesort(L,Ls) :- 
	divide(L,A,B), 
	mergesort(A,AA),
	mergesort(B,BB), 
	merge(AA,BB,Ls).

divide(A,B,C):- 
	length(A,N), 
	NN is N // 2, 
	divide(A,NN,B,C).

divide(A,0,[],A):-!.     % <---  corrigido

divide([X|R],N,[X|S],C) :- 
	M is N - 1, 
	divide(R,M,S,C).

merge([],A,A):-!.
merge(A,[],A) :-!.

merge([A|R], [B|S], [A|X]) :- 
	A =< B,                    % <-----  corrigido
	!, 
	merge(R,[B|S],X).  

merge([A|R], [B|S], [B|X]) :- 
	B < A,
	!, 
	merge([A|R],S,X).