sorting.hs

-- Insertion sort
inssort :: Ord a => [a] -> [a]
inssort []     = []
inssort (x:xs) = insert x (inssort xs)
    where
        insert :: Ord a => a -> [a] -> [a]
        insert n [] = [n]
        insert n (x:xs)
            | n <= x    = n : x : xs
            | otherwise = x : insert n xs

-- Insertion sort (higher order version)
inssortBy :: Ord b => (a -> b) -> [a] -> [a]
inssortBy f []     = []
inssortBy f (x:xs) = insertBy f x (inssortBy f xs)
    where
        insertBy :: Ord b => (a -> b) -> a -> [a] -> [a]
        insertBy f n [] = [n]
        insertBy f n (x:xs)
            | f n <= f x = n : x : xs
            | otherwise  = x : insertBy f n xs

-- Quicksort
qsort :: Ord a => [a] -> [a]
qsort []     = []
qsort (x:xs) = qsort (less x xs) ++ occs x (x:xs) ++ qsort (more x xs)
    where
        less n xs = [x | x <- xs, x < n]
        occs n xs = [x | x <- xs, x == n]
        more n xs = [x | x <- xs, x > n]

-- Quicksort (higher order version)
qsortBy :: Ord b => (a -> b) -> [a] -> [a]
qsortBy f []     = []
qsortBy f (a:xs) = qsortBy f less ++ occs ++ qsortBy f more
    where
        less = [x | x <- xs, f x < f a]
        occs = a : [x | x <- xs, f x == f a]
        more = [x | x <- xs, f x > f a]

-- Merge sort
msort :: Ord a => [a] -> [a]
msort []  = []
msort [x] = [x]
msort xs  = merge (msort ys) (msort ws)
    where
        (ys,ws) = (take l xs, drop l xs)
        l = length xs `div` 2

merge :: Ord a => [a] -> [a] -> [a]
merge [] ys         = ys
merge xs []         = xs
merge (x:xs) (y:ys) = if x < y then x : merge xs (y:ys) else y : merge (x:xs) ys