ObjPtr numbers  class_is array

: ?Exchange { L-idx R-idx -- L-idx R-idx }
	L-idx R-idx = if L-idx R-idx exit then
    L-idx at: numbers R-idx at: numbers \ l-val r-val
    2dup = if 2drop L-idx R-idx exit then
    L-idx to: numbers R-idx to: numbers
    L-idx R-idx ;

: partition ( l r -- l1 r1 l2 r2 )
  2dup + 2/ at: numbers  >r ( r: -- pivot )
  2dup
  begin
  	swap begin dup at: numbers r@ ( pivot ) < while 1+ repeat
  	swap begin r@  ( pivot ) over at: numbers < while 1- repeat
	2dup <= if ?Exchange swap 1+ swap 1- then
	2dup >
  until
  r> drop \ throw pivot away
  swap rot ;
 
: (qsort) ( l r -- )
	2dup >= if 2drop exit then
	partition
	( l2 r2 ) recurse
	( l1 r1 ) recurse \ tail recursion!
;

: qsort
-> numbers
0 limit: numbers 1- (qsort) ;

30000 array s2
: ready
30000 0 DO 30000 random i to: s2 LOOP
;


\ ready 
\ s2 qsort