:- module(_,[qsort/2],[assertions,regtypes,nativeprops]).

:- entry qsort(A,B) : ( numlist(A), var(B) ).
:- pred qsort(A,B) : ( numlist(A), var(B) ).

qsort(A, B) :- qsort_(A,B).

:- pred qsort_(L1, L2) : numlist(L1) => list(L2).

qsort_([],[]).
qsort_([X|L],R) :-
        partition(L,X,L1,L2),
        qsort_(L2,R2),
        qsort_(L1,R1),
        append(R1,[X|R2],R).

:- pred partition/4 : numlist * num * term    * term
                   => numlist * num * numlist * numlist.

partition([],_,[],[]).
partition([E|R],C,[E|Left1],Right) :-
        less(E,C),
        partition(R,C,Left1,Right).
partition([E|R],C,Left,[E|Right1]) :-
        greatereq(E,C),
        partition(R,C,Left,Right1).

:- pred append/3 : list * list * term
                => list * list * list.

append([],X,X).
append([H|X],Y,[H|Z]) :-
        append(X,Y,Z).

:- pred less/2 : num * num.

less(E,C) :-
        E<C.

:- pred greatereq/2 : num * num.

greatereq(E,C) :-
        E>=C.

:- regtype numlist/1.

numlist([]).
numlist([A|B]) :-
        num(A),
        numlist(B).
