Haskell性能：反转计数算法

我决定使用 Haskell从Standford算法课程 https://class.coursera.org/algo-005解决第一个编程任务.尽管我对语言很陌生,但我实现它的速度要快于c.我有6年的工作经验,所以给我留下了深刻的印象.但表现令人失望：0.19秒(c)vs 9.88(haskell)版本.
如何提高Haskell实现的性能,使其可以与c相媲美？

这是我在Haskell中的代码

data SortedList = SortedList {
    inversionCount :: Int,
    list :: [Int]
} deriving (Show) 

--      first   list        accumulator
packm :: Int -> SortedList -> Int -> SortedList
packm x (SortedList count xs) add =  SortedList (count + add) (x:xs)

merge2 :: [Int] -> [Int] -> SortedList
merge2 [] xs = SortedList 0 xs
merge2 xs [] = SortedList 0 xs
merge2 xlist@(x:xs) ylist@(y:ys)
    | x < y = packm x (merge2 xs ylist) 0
    | otherwise = packm y (merge2 xlist ys) $length xlist

countAndMerge :: SortedList -> SortedList -> SortedList
countAndMerge (SortedList lcount lxs) (SortedList rcount rxs) =
    let merged = merge2 lxs rxs
    in SortedList (lcount + rcount + inversionCount merged) $list merged

mergesort :: [Int] -> SortedList
mergesort [] = SortedList 0 []
mergesort [x] = SortedList 0 [x]
mergesort xs =
    let leftsorted = mergesort $take halfElements xs
        rightsorted = mergesort $drop halfElements xs
    in countAndMerge leftsorted rightsorted
    where halfElements = length xs `div` 2

main = do 
    contents <- getContents
    let intlist = [ read x :: Int | x <- (lines contents) ]
    print $inversionCount $mergesort intlist

最大的问题是渐近的表现是不正确的;它是O(n ^ 2 * log n)而不是最优O(n * log n).罪魁祸首是merge2：

| otherwise = packm y (merge2 xlist ys) $length xlist

长度xlist是O(n).假设一个随机输入列表,我们需要在大约一半merge2调用上计算长度xlist,从而使一个级别的合并O(n ^ 2).