% From the book
% PROLOG PROGRAMMING IN DEPTH
% by Michael A. Covington, Donald Nute, and Andre Vellino
% (Prentice Hall, 1997).
% Copyright 1997 Prentice-Hall, Inc.
% For educational use only

% File MSORT.PL
% Mergesort


% mergesort(+List1,-List2)
%  Sorts List1 giving List2 using mergesort.

mergesort([First,Second|Rest],Result) :-   % list has at least 2 elements
  !,
  partition([First,Second|Rest],L1,L2),
  mergesort(L1,SL1),
  mergesort(L2,SL2),
  mergelist(SL1,SL2,Result).

mergesort(List,List).                      % list has 0 or 1 element



% mergelist(+List1,+List2,-Result)
%  Combines two sorted lists into a sorted list.

mergelist([First1|Rest1],[First2|Rest2],[First1|Rest]) :-
  First1 @< First2,
  !,
  mergelist(Rest1,[First2|Rest2],Rest).

mergelist([First1|Rest1],[First2|Rest2],[First2|Rest]) :-
  \+ First1 @< First2,
  !,
  mergelist([First1|Rest1],Rest2,Rest).

mergelist(X,[],X).

mergelist([],X,X).



% partition(+List,-List1,-List2)
%  splits List in two the simplest way,
%  by putting alternate members in different lists

partition([First,Second|Rest],[First|F],[Second|S]) :-  % 2 or more elements
   !,
   partition(Rest,F,S).

partition(List,List,[]).                                % 0 or 1 element



% Demonstration predicate

testsort :- mergesort([7,0,6,5,4,9,4,6,3,3],What), write(What).