gistfile1.hs

import qualified Data.List as List

sort cmp lst = mergeMany (map return lst) []
  where
    merge (xs@(x:xs')) (ys@(y:ys')) !zs =
      case y `cmp` x of
        LT -> merge xs  ys' (y:zs)
        _  -> merge xs' ys  (x:zs)
    merge xs ys zs = reverseAppend zs $! xs ++ ys

    mergeMany   [] []       = []
    mergeMany [xs] []       = xs
    mergeMany   [] [ys]     = ys
    mergeMany (a:b:xss) yss = mergeMany xss $! merge a b [] : yss
    mergeMany xss yss       = mergeMany (xss ++ yss) []

    reverseAppend xs ys = go xs ys
      where
        go []     ys = ys
        go (x:xs) ys = go xs $! x:ys