haskell - Haskell 中的合并排序

Question

我是 Haskell 的新手，我正在尝试在其中实现一些已知的算法。

我已经对字符串实现了合并排序。我有点失望我的 Haskell 实现与 C 和 Java 实现相比的性能。在我的机器(Ubuntu Linux，1.8 GHz)上，C(gcc 4.3.3)在 1.85 秒内对 1 000 000 个字符串进行排序，Java (Java SE 1.6.0_14) 需要 3.68 秒，Haskell (GHC 6.8.2) 需要 25.89 秒。对于较大的输入(10 000 000 个字符串)，C 需要 21.81 秒，Java 需要 59.68 秒，Haskell开始交换，我希望在几分钟后停止该程序。

由于我是 Haskell 的新手，我有兴趣知道我的实现是否可以提高时间/空间效率。

预先感谢您的任何提示乔吉奥

我的实现:

merge :: [String] -> [String] -> [String]
merge [] ys = ys
merge xs [] = xs
merge (x:xs) (y:ys) = if x < y
                        then x : (merge xs (y:ys))
                        else y : (merge (x:xs) ys)

mergeSort :: [String] -> [String]
mergeSort xs = if (l < 2)
                 then xs
                 else merge h t
               where l = length xs
                     n = l `div` 2
                     s = splitAt n xs
                     h = mergeSort (fst s)
                     t = mergeSort (snd s)

Answer 1

尝试这个版本:

mergesort :: [String] -> [String]
mergesort = mergesort' . map wrap

mergesort' :: [[String]] -> [String]
mergesort' [] = []
mergesort' [xs] = xs
mergesort' xss = mergesort' (merge_pairs xss)

merge_pairs :: [[String]] -> [[String]]
merge_pairs [] = []
merge_pairs [xs] = [xs]
merge_pairs (xs:ys:xss) = merge xs ys : merge_pairs xss

merge :: [String] -> [String] -> [String]
merge [] ys = ys
merge xs [] = xs
merge (x:xs) (y:ys)
 = if x > y
        then y : merge (x:xs)  ys
        else x : merge  xs    (y:ys)

wrap :: String -> [String]
wrap x = [x]

1. 坏主意是先拆分列表。而不是只列出一个成员列表。 Haskell 很懒，到了合适的时间就会完成。
2. 然后合并多对列表，直到只剩下一个列表。