Bottom-up natural mergesort in Haskell

msort.hs

module Msort (msortBy, msort) where

msortBy :: (a -> a -> Ordering) -> [a] -> [a]
msortBy orderOp =
  foldr merge [] . foldr mergeStack [] . runs
  where
    -- mergeStack :: [a] -> [[a]] -> [[a]]
    --   mergeStack "k" [ "" "ij" "" "abcdefgh" ] = [ "k" "ij" "" "abcdefgh" ]
    --   mergeStack "l" [ "k" "ij" "" "abcdefgh" ] = [ "" "" "ijkl" "abcdefgh" ]
    mergeStack x ([]:s) = x:s
    mergeStack x (y:s) = []:mergeStack (merge x y) s
    mergeStack x [] = [x]
    -- merge :: [a] -> [a] -> [a]
    merge xx@(x:xs) yy@(y:ys)
      | orderOp x y /= GT = x:merge xs yy
      | otherwise = y:merge xx ys
    merge x [] = x
    merge [] y = y
    -- runs :: Ord a => [a] -> [[a]]
    runs (x:xs) = collectRun x x (x:) xs
    runs [] = []
    -- collectRun :: Ord a => a -> a -> ([a] -> [a]) -> [a] -> [[a]]
    collectRun mn mx f (x:xs)
      | orderOp x mn == LT = collectRun x mx (\y -> x:(f y)) xs -- prepend
      | orderOp x mx /= LT = collectRun mn x (\y -> f (x:y)) xs -- append
    collectRun mn mx f x = f [] : runs x

msort :: Ord a => [a] -> [a]
msort = msortBy compare

You can uncomment your local type signatures if you enable {-# LANGUAGE ScopedTypeVariables #-} and use msortBy :: forall a . (a -> a -> Ordering) -> [a] -> [a].