(* Comments   M-x sml-skip-errors
              C-x `                     Jump to next error

*)


(*
quicksort : int list -> int list
quicksort xs = ys

Invariant:
ys are sorted  version of xs

*)

fun quicksort [] = []
  | quicksort (pivot :: xs) = partition (pivot, xs, [], [])

(* partition : int * int list * int list * int list -> int list 

   partition (pivot, xs, lt, ge) = s 
*)
and partition (pivot:int, [], lt, ge) =
     (quicksort lt) @ [pivot] @ (quicksort ge)
  | partition (pivot:int, x::xs, lt, ge) =
    if x<pivot then partition (pivot, xs, x::lt, ge)
    else partition (pivot, xs, lt, x::ge)
    





val test = quicksort [3,12,5,1,9,8]