!TITLE Quick-Sort
!KEY
The  goal  qsort(L,[],R)  is true if list R is a sorted version of list L. More
generally, qsort(L,R0,R) is true if list R consists of the members  of  list  L
sorted  into order, followed by the members of list R0. The algorithm used is a
variant of Hoare's "Quick Sort".

    |
    | qsort([X|L],R0,R) :-
    |    partition(L,X,L1,L2),
    |    qsort(L2,R0,R1),
    |    qsort(L1,[X|R1],R).
    | qsort([],R,R).
    |
    | partition([X|L],Y,[X|L1],L2) :- X =< Y, !,
    |    partition(L,Y,L1,L2).
    | partition([X|L],Y,L1,[X|L2]) :- X > Y, !,
    |    partition(L,Y,L1,L2).
    | partition([],_,[],[]).