quicksort ( seq from to quot: ( obj1 obj2 -- <=> ) -- )

Vocabulary

sorting.quick.private

Inputs

seq	an object
from	an object
to	an object
quot	a quotation with stack effect ( obj1 obj2 -- <=> )

Outputs

None

Definition

USING: kernel math math.order math.private sequences.private ;

IN: sorting.quick.private

:: quicksort ( seq from to quot: ( obj1 obj2 -- <=> ) -- )
    from to < [
        from to fixnum+fast 2/ seq nth-unsafe :> pivot from to
        [ 2dup <= ] [
            [ over seq nth-unsafe pivot quot call +lt+ eq? ]
            [ [ 1 fixnum+fast ] dip ] while
            [ dup seq nth-unsafe pivot quot call +gt+ eq? ]
            [ 1 fixnum-fast ] while 2dup <= [
                [ seq exchange-unsafe ]
                [ [ 1 fixnum+fast ] [ 1 fixnum-fast ] bi* ] 2bi
            ] when
        ] while [ seq from ] dip quot quicksort [ seq ] dip
        to quot quicksort
    ] when ; inline recursive