Warum funktionieren meine beiden Codes so unterschiedlich? (Haskell, Merge Sort)

Question

Ich schrieb einen Code für merge sort (Haskell).

Ich habe eine Frage zu der Funktion, die zwei Listen entsprechend der Reihenfolge zusammenstellt.

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

Das ist mein Original-Code ist. (Xs, ys sind die Parameter und zs ist ein Akkumulator.)

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]) 

Dies ist mein zweiter Code, den ich schrieb, nachdem ein Code Bezug fand ich online.

Nur mit diesem kleinen Unterschied verbesserte sich mein Code sehr.

Ich sortierte eine Liste von ungefähr 500 Wörtern und mein ursprünglicher Code benötigt ungefähr 2,5 Sekunden, aber der neue sortiert es Durchschnitt innerhalb von 0,4 Sekunden.

Ich frage mich, warum meine ist so langsam, während der Online ist viel schneller, obwohl sie ziemlich ähnlich aussehen. (Ich dachte sogar, dass meins wäre schneller, weil meins nicht hin und her gehen muss.)

Vielen Dank im Voraus.

Answer 1

Prepending (:) auf eine Liste ist O (1), (++) ist O (n), wobei n eine Länge einer linken Liste ist

als zs größer bekommen Sie die ganze Liste durchlaufen haben Jedes Mal, nur um ein Element hinzuzufügen [x]