爲什麼我的兩個代碼工作如此不同？ （Haskell，合併排序）

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]