%%% Quick sort in Prolog

partition(_, [], [], []).
partition(P, [H|T], [H|L], R) :-
    H =< P,
    partition(P, T, L, R).
partition(P, [H|T], L, [H|R]) :-
    H > P,
    partition(P, T, L, R).

%%% quicksort(+L, -S): S is the sorted version of list L

quicksort([], []).
quicksort([H|T], S) :-
    partition(H, T, L, R),
    quicksort(L, SL),
    quicksort(R, SR),
    append(SL, [H|SR], S).