insert(A,[],[A]).
insert(A,[B|X],[A,B|X]) :- A @=< B,!.
insert(A,[B|X],[B|Z]) :- insert(A,X,Z).

insSort([],[]).
insSort([A|X],Z) :- insSort(X,Z1), insert(A,Z1,Z).

cat([],Y,Y).
cat([A|X],Y,[A|Z]) :- cat(X,Y,Z).

part(_,[],_,_).
part(A,[B|X],[B|Y],Z) :- B @=< A,!, part(A,X,Y,Z).
part(A,[B|X],Y,[B|Z]) :- part(A,X,Y,Z).

qsort([],[]).
qsort([A|X],Z) :- part(A,X,Z0,Z1), 
                  qsort(Z0,SZ0),
                  qsort(Z1,SZ1),
		  cat(SZ0,[A|SZ1],Z).

nrands(_,0,[]).
nrands(R,N,[A|X]) :- A is random(R), N1 is N-1, nrands(R,N1,X).

ordered([]).
ordered([A]).
ordered([A,B|X]) :-  A =< B, ordered([B|X]).

testsort(R,N,P) :- nrands(R,N,X0), 
                 T0 is cputime,
                 call(P,X0,X1),
                 T1 is cputime,
                 ordered(X1),
                 Tdiff is (T1 - T0),
                 write(Tdiff).