An attempt at an bottom-up functional representation of mergesort

mergesort.hs

import Control.Arrow
import Data.List
import Data.Function

main = interact (show.(mergeSort (<=)).head.lines)

merge :: (a -> a -> Bool) -> [a] -> [a] -> [a]
merge _ xs [] = xs
merge _ [] ys = ys
merge p (x:xs) (y:ys) =
  if x `p` y then x: merge p xs (y:ys) else y: merge p (x:xs) ys

longer :: [a] -> [a] -> Bool
longer [] _ = False
longer (_:_) [] = True
longer (_:xs) (_:ys) = xs `longer` ys

merge' :: (a -> a -> Bool) -> [[a]] -> [a] -> [[a]]
merge' _ [] ys = [ys]
merge' p (xs:xss) ys =
  if xs `longer` ys then ys:xs:xss else merge' p xss $ merge p xs ys

mergeSort :: (a -> a -> Bool) -> [a] -> [a]
mergeSort p xs = foldl (merge p) [] $ foldl (merge' p) [] $ map (:[]) xs