====== Interchange sort ======
{{tag>sorting algorithms}}
===== Description =====
Sorting by Interchange

**Source**:  The Art of Prolog
===== Download =====
Program source code: {{interchange_sort.pl}}
===== Listing =====
<code prolog>
/*
    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

</code>
===== Comments =====