私の2つのコードはどうして違うのですか？ （Haskell、Merge Sort）

Question

私はマージソート（Haskell）のコードを書いていました。

私は、順序に従って2つのリストをまとめる関数について質問します。

（すなわち、[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）、（++）を使用すると、リスト全体をトラバースする必要がZSが大きくなるにつれて、nは左のリストの長さ

あるO（N）であります毎回1つの要素を追加するだけです[x]