(* Quick Sort, using the first element of the list as the splitting criterion *)

(* Partition (curried): takes a predicate P and a list L and returns a pair of
   lists (Lt,Lf).  Lt contains the elements of L for which P is true; Lf
   contains the elements for which P is false.  *)

fun partition _ [] = ([],[])
 |  partition  P (head::tail) = let val (Ppass,Pfail) = partition P tail
                            in  if (P head)
                                then (head::Ppass,Pfail)
                                else (Ppass,head::Pfail)
                            end
;


fun qsort [] = []
 |  qsort (h::t) =
    let fun lessthanorequal (x: int) y = x <= y   (**)
        val (bigger,smaller) = partition (lessthanorequal h) t   (***)
        val sorted1 = qsort smaller
        val sorted2 = qsort bigger
    in  sorted1 @ (h::sorted2)
    end
;

(* Notes *)
(**  We have to specify a type ("int") because "<" is overloaded.  *)
(*** If "lessthanorequal" had not been curried, we would have needed
     FIRST_ARG to do this *)

(* version of qsort that remove duplicates *)

fun qsortnodups [] = []
 |  qsortnodups (h::t) =
    let fun lessthanorequal (x: int) y = x <= y
        val (bigger,smaller) = partition (lessthanorequal h) t
        val sorted1 = qsortnodups smaller
        val sorted2 = qsortnodups bigger
    in  case sorted2
         of   []  => sorted1 @ [h]
          | (h2::t2)  => if h=h2
                         then sorted1 @ sorted2
                         else sorted1 @ (h::sorted2)
    end
;