Perché i miei due codici funzionano in modo così diverso? (Haskell, Merge Sort)

Question

Stavo scrivendo un codice per l'unge sort (Haskell).

Ho una domanda sulla funzione che mette insieme due elenchi secondo l'ordine.

(vale a dire [1,4,7] [2,5,6] -> [1,2,4,5,6,7])

Questo è il mio codice originale. (Xs, ys sono i parametri e zs è un accumulatore.)

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

Questo è il mio secondo codice che ho scritto dopo aver fatto riferimento un codice che ho trovato on-line.

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

Proprio con questa piccola differenza, il mio codice è migliorato molto.

Stavo ordinando un elenco di circa 500 parole e il mio codice originale ha bisogno di circa 2,5 secondi, ma il nuovo ordina mediamente entro 0,4 secondi.

Mi chiedo perché il mio sia così lento mentre quello online è molto più veloce anche se sembrano abbastanza simili. (Ho anche pensato che il mio sarebbe stato più veloce perché il mio non ha bisogno di andare avanti e indietro.)

Grazie in anticipo.

Answer 1

prepending (:) per una lista è O (1), (++) è O (n), dove n è una lunghezza di una lista di sinistra

come zs si fanno più grandi si deve attraversare l'intera lista ogni volta solo per aggiungere un elemento [x]