Dlaczego moje dwa kody działają tak inaczej? (Haskell, Merge Sort)

Question

Pisałem kod do sortowania korespondencji seryjnej (Haskell).

Mam pytanie dotyczące funkcji, która umieszcza dwie listy razem zgodnie z zamówieniem.

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

to my oryginalny kod. (Xs, ys są parametry i ZS jest akumulator.)

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

To jest mój drugi kod, który napisałem po odwołaniu kod znalazłem w Internecie.

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

Właśnie z tą niewielką różnicą mój kod znacznie się poprawił.

Sortowałem listę około 500 słów, a mój oryginalny kod potrzebował około 2,5 sekundy, ale nowy sortuje średnio w ciągu 0,4 sekundy.

Zastanawiam się, dlaczego mój jest tak powolny, podczas gdy ten w Internecie jest znacznie szybszy, mimo że wyglądają bardzo podobnie. (Myślałem nawet, że moja będzie szybsza, bo moja nie musi tam wracać.)

Z góry dziękuję.

Answer 1

poprzedniki (:) na liście jest O (1), (++) jest O (n), gdzie n to długość lewej liście

jak zs uzyskać większe masz przemierzać całą listę za każdym razem po prostu dodać jeden element [x]