% standard version

quicksort([], []).
quicksort([X|Xs], Sorted) :-
  partition(X, Xs, Smalls, Bigs),
  quicksort(Smalls, SortedSmalls),
  quicksort(Bigs, SortedBigs),
  append(SortedSmalls, [X|SortedBigs], Sorted).


partition(_, [], [], []) :- !.
partition(Pivot, [X|Xs], [X|Ys], Zs) :-
   X =< Pivot, !,
   partition(Pivot, Xs, Ys, Zs).
partition(Pivot, [X|Xs], Ys, [X|Zs]) :-
   partition(Pivot, Xs, Ys, Zs).



% difference list version

quicksort_dl(L, S) :- quicksort_dl_aux(L, S - []).

quicksort_dl_aux([], S - S).

quicksort_dl_aux([X|Xs], Sorted - Tail) :-
  partition(X, Xs, Smalls, Bigs),
  quicksort_dl_aux(Smalls, Sorted - [X|T]),  
  quicksort_dl_aux(Bigs, T - Tail).