% Figure 9.2  Quicksort.


% quicksort( List, SortedList): sort List by the quicksort algorithm

quicksort( [], []).

quicksort( [X|Tail], Sorted)  :-
   split( X, Tail, Small, Big),
   quicksort( Small, SortedSmall),
   quicksort( Big, SortedBig),
   conc( SortedSmall, [X|SortedBig], Sorted).

% split( X,L,Small,Big) if Small contains all elements in L that are
% no bigger than X and Big contains all elements in L that are
% bigger than X.

split( _, [], [], []).

split( X, [Y|Tail], [Y|Small], Big)  :-
   gt( X, Y), !,
   split( X, Tail, Small, Big).

split( X, [Y|Tail], Small, [Y|Big])  :-
   split( X, Tail, Small, Big).

gt( X,Y) :- X > Y.  % greater than for numbers

conc( X,Y,Z) :- append( X,Y,Z).  % append is built in