tshm
6/4/2014 - 9:33 AM

simple mergesort in haskell

simple mergesort in haskell

import Data.List

-- | mergesort of the given list
-- >>> mergesort [3] :: [Int]
-- [3]
--
-- >>> mergesort [3,2,1,5,2,4] :: [Int]
-- [1,2,2,3,4,5]
--
mergesort :: (Ord a) => [a] -> [a]
mergesort (x:[]) = [x]
mergesort zs = merge (mergesort l) (mergesort r) where
  (l,r) = splitAt (length zs `div` 2) zs
  merge xs [] = xs
  merge [] ys = ys
  merge xs@(x:xs') ys@(y:ys') = if x < y
                                then x : merge xs' ys
                                else y : merge xs ys'

main :: IO ()
main = print $ mergesort ([3,5,2,1,5] :: [Int])