Sorting.hs

module Sorting where

-- tail recursive, much better performance
sort :: Ord a => [a] -> [a]
sort xs = loop [xs] [] where
  loop [] ys = ys
  loop ([] : xss) ys = loop xss ys
  loop ((x : xs) : xss) [] = loop (xs : xss) [x]
  loop ((x : xs) : xss) (y : ys) = if x <= y
    then loop (xs : xss) (x : y : ys)
    else loop (reverse (x : ys) : (y : xs) : xss) []

-- shorter, but non tail recursive
sort' :: Ord a => [a] -> [a]
sort' [] = []
sort' (x : xs) = case sort' xs of
  [] -> [x]
  (y : ys) -> if y < x
    then y : sort' (x : ys)
    else x : y : ys