% psort(UL,SL) <=> SL is a sorted version of the list UL
% E.g., sort([4,2,1,3],[1,2,3,4]) is true

% a correct solution is: SL must be ascending
sorted([]).
sorted([_]).
sorted([X,Y|Xs]) :- X =< Y, sorted([Y|Xs]).

% potential solution: SL must contain the same elements as UL,
% but in a different order: SL is a permutation of UL
perm([],[]).
perm(Xs,[Y|Ys]) :- select(Y,Xs,Zs), perm(Zs,Ys).

% select an arbitrary element in a list and remove in the other list.
select(X,[X|Xs],Xs).
select(X,[Y|Xs],[Y|Zs]) :- select(X,Xs,Zs).

psort(UL,SL) :- perm(UL,SL), sorted(SL).