Why my two codes work so differently? (Haskell, Merge Sort)

Question

I was writing a code for merge sort (Haskell).

I have a question on the function that puts two lists together according to the order.

( i.e. [1,4,7] [2,5,6] -> [1,2,4,5,6,7])

This is my original code. (xs, ys are the parameters and zs is an accumulator.)

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

This is my second code which I wrote after referring a code I found online.

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

Just with this small difference, my code improved a lot.

I was sorting a list of around 500 words and my original code needs around 2.5 seconds but the new one sorts it average of within 0.4 second.

I am wondering why mine is so slow while the one online is much faster even though they look pretty similar. (I even thought mine would be faster because mine does not need to go back and forth.)

Thanks in advance.

Answer 1

prepending (:) to a list is O(1), (++) is O(n) where n is a length of a left list

as zs get larger you have to traverse the whole list every time just to add one element [x]