:- module(_,_).

% Quick-sort using standard lists and append
% ------------------------------------------

qsort([],[]).
qsort([X|L],S) :-         % Take first element of list in X
   partition(L,X,LS,LB),  % LS are the elements of L < X
                          % LB are the elements of L >= X
   qsort(LS,LSS),         % LSS is LS sorted 
   qsort(LB,LBS),         % LBS is LB sorted 
   append(LSS,[X|LBS],S). % We append the small ones sorted to 
                          % the big ones sorted (w/X in front)

partition([],_P,[],[]).
partition([E|R],P,[E|Smalls],Bigs) :- % Take first element E
    E < P,            % If E < P add to list of smaller ones
    partition(R,P,Smalls,Bigs).
partition([E|R],P,Smalls,[E|Bigs]) :-
    E >= P,           % If E >= P add to list of larger ones
    partition(R,P,Smalls,Bigs).

% Try:
% ?- qsort([5,2,1,3,7,6], SL).