Sorting by Interchange

Source: The Art of Prolog

Program source code: interchange_sort.pl

/*
    mysort(Xs,Ys) :- 
	Ys is an ordered permutation of the list of integers Xs.
*/
    mysort(Xs,Ys) :-
	append(As,[X,Y|Bs],Xs),
	X > Y,
	!,
	append(As,[Y,X|Bs],Xs1),
	mysort(Xs1,Ys).
    mysort(Xs,Xs) :-
	ordered(Xs), !.
 
	ordered([]).
	ordered([X]).
	ordered([X,Y|Ys]) :- X =< Y, ordered([Y|Ys]).
 
%  Program 11.5   Interchange sort