USING: combinators.short-circuit fry kernel math sequences ;
IN: insertion
! An in-place insertion sort.
! Your sequence is now diamonds.

DEFER: insert

: step ( i seq -- i-1 seq ) [ 1 - ] dip ;
: exchange? ( i seq -- ? ) [ nth ] [ step nth ] 2bi < ;
: insert? ( i seq -- ? ) { [ drop 0 > ] [ exchange? ] } 2&& ;
: (insert) ( i seq -- ) [ dupd step exchange ] [ step insert ] 2bi ;
: insert ( i seq -- ) 2dup insert? [ (insert) ] [ 2drop ] if ;
: insertion-sort ( seq -- ) [ length ] keep '[ _ insert ] each-integer ;