> module MergeSort (mergesort) where

> mergesort :: (Ord a) => [a] -> [a]
> mergesort = mergesort' . map wrap

> mergesort' :: (Ord a) => [[a]] -> [a]
> mergesort' [] = []
> mergesort' [xs] = xs
> mergesort' xss = mergesort' (merge_pairs xss)

> merge_pairs :: (Ord a) => [[a]] -> [[a]]
> merge_pairs [] = []
> merge_pairs [xs] = [xs]
> merge_pairs (xs:ys:xss) = merge xs ys:merge_pairs xss

> merge :: (Ord a) => [a] -> [a] -> [a]
> merge xs [] = xs
> merge [] ys = ys
> merge (x:xs) (y:ys)
>  | x <= y    = x:merge    xs (y:ys)
>  | otherwise = y:merge (x:xs)   ys

> wrap :: a -> [a]
> wrap x = [x]