mergesort

mergesort.hs

{-# LANGUAGE UnicodeSyntax #-}

import Control.Arrow ((***))
import Control.Monad (join)

merge ∷ Ord α => [α] -> [α] -> [α]
merge a [] = a
merge [] a = a
merge xlist@(x:xs) ylist@(y:ys) | x < y     = x : merge xs ylist
                                | otherwise = y : merge xlist ys

mergesort ∷ Ord α => [α] -> [α]
mergesort x@(_:_:_) =
  uncurry merge . join (***) mergesort . (splitAt =<< (`div` 2) . length) $ x
mergesort x = x