qsort.sml

datatype 'a tree
  = Leaf
  | Node of 'a tree * 'a * 'a tree

fun build (op <) =
  let
    fun loop nil = Leaf
      | loop (x :: xs) =
        let
          val (xs, ys) = List.partition (fn y => y < x) xs
        in
          Node (loop xs, x, loop ys)
        end
  in
    loop
  end

fun flatten t =
  let
    fun loop Leaf = (fn xs => xs)
      | loop (Node (l,x,r)) = loop l o (fn xs => x :: xs) o loop r
  in
    loop t nil
  end

fun qsort (op <) = flatten o build (op <)