% 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

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

% perm(Xs,Ys) <=> Ys is a permutation of Xs
perm([],[]).
perm(Xs,[Z|Zs]) :- select(Z,Xs,Ys), perm(Ys,Zs).

% select(Z,Xs,Ys) <=> Z is an element in Xs and Ys are the remaining elements
select(Z,[Z|Xs],Xs).
select(Z,[X|Xs],[X|Ys]) :- select(Z,Xs,Ys).

% overall solution: permutation sort
psort(UL,OL) :- perm(UL,OL), sorted(OL).