module Sort where

-- qsort

partition pred [] = ([], [])
partition pred (x:xs) = if (pred x) then (x:a, b) else (a, x:b)
  where (a, b) = partition pred xs

qsort comp [] = []
qsort comp (x:xs) = (qsort comp more) ++ [x] ++ (qsort comp less)
  where (more, less) = partition (`comp` x) xs

-- mergesort

split [] = ([], [])
split [x] = ([x], [])
split (x:y:rest) = (x:a, y:b) where (a, b) = split rest

merge comp x [] = x
merge comp [] y = y
merge comp a@(x:xs) b@(y:ys) = if (x `comp` y)
                               then x:(merge comp xs b)
                               else y:(merge comp a ys)

mergesort comp [] = []
mergesort comp [x] = [x]
mergesort comp list = merge comp (mergesort comp a) (mergesort comp b)
  where (a, b) = split list