为什么我的两个代码工作方式不同？(Haskell,Merge Sort)

Question

我正在为合并排序(Haskell)编写代码.

我有一个关于根据顺序将两个列表放在一起的函数的问题.

(即[1,4,7] [2,5,6] - > [1,2,4,5,6,7])

这是我的原始代码.(xs,ys是参数,zs是累加器.)

msort4 [] ys zs = zs ++ ys
msort4 xs [] zs = zs ++ xs
msort4 allx@(x:xs) ally@(y:ys) zs 
 | x <= y = msort4 xs ally (zs ++ [x])
 | otherwise = msort4 allx ys (zs ++ [y])

这是我在引用我在网上找到的代码后写的第二个代码.

msort4 [] ys = ys
msort4 xs [] = xs
msort4 allx@(x:xs) ally@(y:ys)
 | x <= y = x :msort4 xs ally 
 | otherwise = y :  msort4 allx ys

只是这个小差异,我的代码改进了很多.

我正在排序大约500个单词的列表,我的原始代码需要大约2.5秒,但新的代码平均在0.4秒内排序.

我想知道为什么我的速度如此之慢,而在线的速度要快得多,即使它们看起来非常相似.(我甚至认为我的速度会更快,因为我不需要来回走动.)

提前致谢.

Answer 1

前置(:)到列表是O(1),(++)是O(n)其中n是左列表的长度

随着zs变大,你每次都要遍历整个列表只是为了添加一个元素[x]