(*
%use "Quicksort/quicksort.fsh" ;;
*)

(* Modified from Bob Tennent's code to be FISh 1.1 compatible.
 and made polymorphic by having a single comparison function cmp,
(strict less_than) instead of <. and >.

*)

let quicksort_pr (cmp: exp a -> exp a -> bool) (array: var [a]) =  
        let rec qs m n = 
          if m>=n then skip
          else 
          new sum = m + n
	  and mid = sum div 2
	  and pivot = array[mid] 
  	  and i = m
	  and j = n
          in 
            whiletrue (cmp array[i]  pivot) ( incr i );  
            whiletrue (cmp pivot array[j]) ( decr j );
            whiletrue (i < j) (
              new aux = array[i] 
              in
                array[i] := array[j];
                array[j] := aux
              end;
              incr i; decr j;
              whiletrue (cmp array[i] pivot) ( incr i );  
              whiletrue (cmp pivot array[j]) ( decr j )
            );
            (if i=j then incr i; decr j else skip);
            qs m (!j) ; qs (!i) n 
          end
      in qs 0 (lendim #array -1) 
      ;;

      let quicksort cmp = ap2er (quicksort_pr cmp);;

(*
      let arg = fill {8:float_shape} with [2.0,3.0,1.0,2.0,5.0,5.0,3.0,6.0];;
      let result = quicksort less_than_float arg ;;
       %run  result;;
*)

let benchmark (k:size) = 
  new seed = 0 in 
  let next = seed := !seed * 25173 + 17431 in 
  new #v = {k * 10000:float_shape} in 
    for i< k * 10000 do
      next ;
      v[i] := int2float seed 
    done ;
    quicksort_pr less_than_float v
  end
  end 
;;