Haskell中的合并排序
Haskell中的合并排序
提问于 2009-08-01 00:08:51
我是Haskell的新手，我正在尝试在其中实现一些已知的算法。
我已经在字符串上实现了合并排序。与C和Java实现相比，我对我的Haskell实现的性能有点失望。在我的机器上(Ubuntu Linux，1.8 GHz)，C (gcc 4.3.3)在1.85秒内排序1000000个字符串，Java (Java 1.6.0_14)在3.68s内排序，Haskell (GHC6.8.2)在25.89s内排序。在较大的输入(10000000个字符串)下，C花费21.81s，Java花费59.68s，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)页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/1215432
复制相关文章
相似问题
腾讯云开发者
