% qsort(+List,-SortedList)

% idea: take the unsorted list, choose a pivot - conveniently the
% first element of the list - split the unsorted list in two distinct
% lists in a way that every element smaller than the pivot goes to the
% first list, and every element greater than the pivot goes to the
% second list. Sort the two resulting lists.

qsort([],[]).              % sorting an empty list returns an empty list
qsort([H|Hs],S) :-         % use H as the pivot
   partition(Hs,H,L1,L2),  % partition produces L1 with values < H, and L2 with values > H
   qsort(L1,S1),           % sort L1
   qsort(L2,S2),           % sort L2
   append(L1,[H|L2],S).    % S is the result of appending L1 and L2 keeping H in between

% partition(+List,+Pivot,-SmalThanPivot,-GreatThanPivot)

partition([],_H,[],[]).          % base case, H is not important. Partition of an empty list results in two empty lists
partition([Y|Ys],H,[Y|L1],L2) :- % if Y =< H put Y in L1
   Y =< H,
   partition(Ys,H,L1,L2).        % recursive predicate will build the rest
partition([Y|Ys],H,L1,[Y|L2]) :- % if Y > H put Y in L2
   Y > H,
   partition(Ys,H,L1,L2).        % recursive predicate will build the rest

% Alternative, more efficient way of implementing partition
partition([],_H,[],[]).
partition([Y|Ys],H,[Y|L1],L2) :- % if Y =< H put Y in L1
   Y =< H, !,                    % use the cut to prune the next clause
   partition(Ys,H,L1,L2).        % recursive predicate will build the rest
partition([Y|Ys],H,L1,[Y|L2]) :- % if Y > H put Y in L2
   partition(Ys,H,L1,L2).        % recursive predicate will build the rest

% because of the cut in the second clause, if Y =< H succeeds, no more alternatives 
% for partition should be executed in case of backtracking