Quick sort

quick_sort.sml

(* Quick Sort *)
exception QuickSortException;
fun qsort nil      = nil
  | qsort (x::nil) = x::nil
  | qsort (x::xs)  = 
    let
      fun fst_pair (a, b) = a
      fun snd_pair (a, b) = b
      
      fun max nil      = raise QuickSortException
        | max (x::nil) = x
        | max (x::xs)  = let val maxxs = max xs in if x > maxxs then x else maxxs end
      fun min nil      = raise QuickSortException
        | min (x::nil) = x
        | min (x::xs)  = let val minxs = min xs in if x < minxs then x else minxs end
      
      fun pivot nil      = raise QuickSortException
        | pivot (x::nil) = x
        | pivot (x::xs)  = ((max (x::xs) - min (x::xs)) div 2) + min (x::xs)
    
      fun partition (pivot, nil)    = (nil, nil)
        | partition (pivot, x::nil) = if x > pivot then (nil, (x::nil)) else ((x::nil), nil)
        | partition (pivot, x::xs)  = 
      let
        val pair = partition (pivot, xs)
        val lt   = fst_pair pair
        val gt   = snd_pair pair
      in
        if pivot < x then (lt, (x::gt)) else ((x::lt), gt)
      end
    
      val hd_xs = hd xs
      val pair = partition ((pivot (x::xs)), (x::xs))
  in
    if length (x::xs) = 2
    then if hd_xs < x then [hd_xs, x] else [x, hd_xs]
    else (qsort (fst_pair pair)) @ (qsort (snd_pair pair))
  end;

qsort [5, 1, 2, 4, 1, 3];
(* val it = [1,1,2,3,4,5] : int list *)