% Predicate psort(UL,SL) <=> SL is a sorted version of integer list UL

% correct solution: all elements in increasing order
sorted([]).
sorted([_]).
sorted([E1,E2|L]) :- E1 =< E2, sorted([E2|L]).


% potential solutions: permutation of the given list UL
perm([],[]).
perm(Xs,[Z|Zs]) :- select(Z,Xs,Ys), perm(Ys,Zs).

% select an element in a list and delete it in the other list (third argument):
select(X,[X|Xs],Xs).
select(X,[Y|Xs],[Y|Ys]) :- select(X,Xs,Ys).

% complete solution: guess some permutation and test whether it is sorted:
psort(UL,SL) :- perm(UL,SL), sorted(SL).