(* CS 362, Lab 2 *)
(* Author: Gabriel Anderson *)


fun last (x::[]) = x
  | last (x::xs) = last xs


fun middle lst =
  let
    fun middle' (x::_)  []         = x
      | middle' (x::_)  (_::[])    = x
      | middle' (_::xs) (_::_::ys) = middle' xs ys
  in
    middle' lst lst
  end


fun median(a,b,c) =
  let
    val M = Int.max(a, Int.max(b, c))
    val m = Int.min(a, Int.min(b, c))
  in
    (a + b + c) - M - m
  end


fun partition (lst, p) =
  let
    fun go (a, (xs, ys)) =
        if a <= p then
          (a::xs, ys)
        else
          (xs, a::ys)
  in
    foldr go ([],[]) lst
  end


fun quicksort []     = []
  | quicksort [x]    = [x]
  | quicksort (p::lst) =
      let
        val (xs, ys) = partition (lst, p)
      in
        quicksort xs @ (p :: quicksort ys)
      end