% -*- Prolog -*-
%
% mergesort
%
%  from "The Craft of Prolog" -- Richard A. O'Keefe
%
% $Id: 047,v 1.1 2000/11/12 12:22:46 peteg Exp $

main :- msort([27, 74, 17, 33, 94, 18, 46, 83, 65, 2, 32, 53, 28, 85, 99,
	47, 28, 82, 6, 11, 55, 29, 39, 81, 90, 37, 10, 0, 66, 51, 7, 21, 85,
	27, 31,	63, 75, 4, 95, 99, 11, 28, 61, 74, 18, 92, 40, 53, 59, 8], X),
	write(X), nl.

msort([], []) :- !.
msort(List, Answer) :-
	length(List, Length),
	msort(Length, List, Answer, []).

msort(1, [X|Rest], [X], Rest) :- !.
msort(2, [X,Y|Rest], Answer, Rest) :-
	!,
	sort2(X, Y, Answer).
msort(N, List, Answer, Rest) :-
	A is N // 2,	msort(A, List, X, Middle),
	Z is N - A,	msort(Z, Middle, Y, Rest),
	merge(X, Y, Answer).

% Glib sort pair predicate -- not robust.

sort2(X, Y, Answer) :-
	X =< Y,
	!,
	Answer = [X, Y].
sort2(X, Y, [Y, X]).


merge([H1|T1], [X|L2], [X|M1]) :-
	X < H1,
	!,
	merge([H1|T1], L2, M1).
merge([X|L1], L2, [X|M1]) :-
	!,
	merge(L1, L2, M1).
merge([], L2, L2).


% Support predicates
length(List, Length) :-
	length(List, 0, Length).

length([], L0, L0).
length([_|Xs], L, L0) :-
	L1 is L + 1,
	length(Xs, L1, L0).
