quicksort.hs

qsort xs = qsort' xs []

qsort' xs rs = case xs of
  []      -> rs
  [x]     -> x:rs
  (x:xs') ->
    let m = median xs in qsort'' xs m rs [] [] []

qsort'' xs m rs ls es gs = case xs of
  [] -> qsort' ls $ es ++ qsort' gs rs
  (x:xs')
    | x > m     -> qsort'' xs' m rs ls es (x:gs)
    | x < m     -> qsort'' xs' m rs (x:ls) es gs
    | otherwise -> qsort'' xs' m rs ls (x:es) gs

median (x:xs) =
  let
    l = length xs - 1
    m = div l 2
  in median' x (xs !! m) (xs !! l)

median' a b c
  | a <= b && b <= c = b
  | a <= b && c < b = c
  | a <= c = a
  | otherwise = c