Quick Sort in Standard ML

qsort.sml

(* クイックソート *)
(* val qsort = fn : ('a * 'a -> order) -> 'a list -> 'a list *)
(* val takePivot = fn : ('a * 'a -> order) -> 'a list -> 'a *)
fun qsort compare nil = nil
  | qsort compare [x] = [x]
  | qsort compare xs = 
  let
    val pivot = takePivot compare xs;
    val (ys, zs) = List.foldr (
      fn (v, (ys, zs)) => 
        case (compare (v, pivot)) 
          of LESS    => (v::ys,    zs)
           | EQUAL   => (   ys,    zs)
           | GREATER => (   ys, v::zs)
    ) (nil, nil) xs;
  in
    (qsort compare ys) @ [pivot] @ (qsort compare zs)
  end
and takePivot compare xs = let
  val n = List.length xs;
  
  fun op< (lhs, rhs) = compare (lhs, rhs) = LESS;
  
  fun medianFromTriple (p, q, r) =
    if p < q
      then (if q < r then q else (if r < p then p else r))
      else (if p < r then p else (if q < r then r else q));
in
  medianFromTriple (
    List.nth (xs, 0),
    List.nth (xs, n div 2),
    List.nth (xs, n - 1)
  )
end;

(* 使用例 *)
(* 比較付き整数 *)
structure OrderedInt :> ORD_KEY 
  where type ord_key = Int.int
= struct
  type ord_key = Int.int;
  
  fun compare (lhs, rhs) = 
    if lhs = rhs
      then EQUAL
      else 
        if lhs < rhs then LESS else GREATER; 
end;

val xs = qsort OrderedInt.compare [8, 4, 6, 7, 2, 3, 1, 9, 5];
(* val xs = [1,2,3,4,5,6,7,8,9] *)