fun ascendCheck([],_) = true
  | ascendCheck([x],_) = true
  | ascendCheck(x::y::xs,lesseq) = 
      lesseq(x,y) andalso ascendCheck(y::xs,lesseq);

fun ascendCheck2(x,lesseq)=
  let fun ac([])=true
        | ac([x])=true
        | ac(x::y::xs) = lesseq(x,y) andalso ac(y::xs);
  in ac(x) end;

fun member(x,[])  =  false
  | member(x,y::l)  =  (x=y) orelse member(x,l);

(*** Sorting ***)

(** ins(3.0,[1.0,2.0,4.0,5.0],op<=) **)

(** insertion sort **)
fun ins (x, [], _) = [x]
  | ins (x, y::ys, lesseq) = 
      if lesseq(x,y) then x::y::ys
                     else y::ins(x,ys, lesseq);

(** insort([3.0,1.0,5.0,4.0,2.0],op<=) **)
(** insort([3,1,5,4,2],op<=) **)
(** insort(["dog","cat","ape"],op<=) **)

fun insort ([],lesseq) = []
  | insort (x::xs,lesseq) = ins(x, insort(xs, lesseq),lesseq);

fun insort2 ([],_) = []
  | insort2 (x::xs,lesseq) = 
    let fun ins (x, []) = [x]
          | ins (x, y::ys) = 
              if lesseq(x,y) then x::y::ys
                             else y::ins(x,ys);
    in ins(x, insort2(xs, lesseq)) end;

fun insort3 (x,lesseq) =
    let fun ins (x, []) = [x]
          | ins (x, y::ys) = 
              if lesseq(x,y) then x::y::ys
                             else y::ins(x,ys);
        fun insort ([]) = []
          | insort (x::xs) = ins(x,insort(xs));
    in insort(x) end;

(** Top-down merge sort **)

fun merge([],ys,_) = ys
  | merge(xs,[],_) = xs
  | merge(x::xs, y::ys,lesseq) =
      if lesseq(x,y) then x::merge(xs,y::ys,lesseq)
                     else y::merge(x::xs,ys,lesseq);

(** tmergesort([3.0,1.0,5.0,4.0,2.0],op<=) **)
(** tmergesort([3,1,5,4,2],op<=) **)
(** tmergesort(["dog","cat","ape"],op<=) **)

fun tmergesort([],_) = []
  | tmergesort([x],_) = [x]
  | tmergesort(xs,lesseq) =
      let val k = length xs div 2
      in  merge(tmergesort(List.take(xs,k),lesseq),
                tmergesort(List.drop(xs,k),lesseq),
                lesseq)
      end;

(** quick([3.0,1.0,5.0,4.0,2.0],op<=) **)
(** quick([3,1,5,4,2],op<=) **)
(** quick(["dog","cat","ape"],op<=) **)

(*quicksort*)
fun quick([],_) = []
  | quick([x],_) = [x]
  | quick (pivot::bs,lesseq) =  
    let fun partition(left,right,[],lesseq) = 
               (quick(left,lesseq)) @ (pivot::quick(right,lesseq))
          | partition(left,right,x::xs,lesseq) =
               if lesseq(x,pivot) then partition (x::left,right,xs,lesseq)
                                  else partition (left,x::right,xs,lesseq)
    in partition([],[],bs,lesseq) end;

fun quick2(x,lesseq) =
  let fun quick([]) = []
        | quick([x]) = [x]
        | quick (pivot::bs) =
      let fun partition(left,right,[]) = 
               (quick(left)) @ (pivot::quick(right))
          | partition(left,right,x::xs) =
               if lesseq(x,pivot) then partition (x::left,right,xs)
                                  else partition (left,x::right,xs)
      in partition([],[],bs) end;
  in quick(x) end;