% ==========================================================================
% $Id: list_sort.pl,v 1.1 2014/01/21 04:50:36 jlang Exp $
% CSI2120 example Code for lecture 5
% ==========================================================================
% (C)opyright:
%
%   Jochen Lang
%   EECS, University of Ottawa
%   800 King Edward Ave.
%   Ottawa, On., K1N 6N5
%   Canada. 
%   http://www.eecs.uottawa.ca/~jlang
% 
% Creator: jlang (Jochen Lang) based on Clocksin & Mellish
% Email:   jlang@eecs.uottawa.ca
% ==========================================================================
% $Log: list_sort.pl,v $
% Revision 1.1  2014/01/21 04:50:36  jlang
% Added further list processing for lecture 5.
%
% ==========================================================================
sortList([],[]).
sortList([P|Q],T) :- partitionList(P,Q,G,D),
		sortList(G,GG), 
                sortList(D,DD),
		append(GG,[P|DD],T). % library predicate

partitionList(P,[X|L],[X|PG],PD) :- X @< P,   
                partitionList(P,L,PG,PD).
partitionList(P,[X|L],PG,[X|PD]) :- X @>= P, 
                partitionList(P,L,PG,PD).
partitionList(P,[],[],[]).