%
% permutation based insert sort  psort(Input,SortedOutput)
%

% delete( X, L, LwithoutX ) 

del( X, [X|LwithoutX] , LwithoutX ) . 
del( X, [H|L], [H|LwithoutX] ) :- del( X, L, LwithoutX ) . 

perm( [] , [] ) . 
perm( L , [H|T] ) :- del( H, L, LwithoutH ) , perm( LwithoutH, T  ) . 

psort( [] , [] ) . 
psort( L , [H|T] ) :- lmax( L, H ) ,            % filter 
                      del( H, L, LwithoutH ) , psort( LwithoutH, T  ) . 

lmax( [X], X ) . 
lmax( [X,X2|Xs] , M ) :- maxi(X,X2,M2) , lmax( [M2|Xs] , M ) . 

maxi(X,Y,X) :- X >= Y .
maxi(X,Y,Y) :- X < Y . 

go(L) :- psort( [45,23,76,68,5,24,13,25,67,84,97,63,57,86,9,88,
                 87,81,72,39,83,48,55,66,18,35,42,17,1,80,10,27,
                 33,53,75,22,20,30,40,91,71,61,50,60,70,41,31,98,
                 90,92,32,62,52], L ).