I am confused why this implementation of mergesort isn't working?

Question

I am a novice in Haskell and I am trying to implement mergesort but it is not working, and I am confused as to why?

My code:

halve :: [a] -> ([a],[a])
halve xs = splitAt (length xs `div` 2) xs

merge :: [Int] -> [Int] -> [Int]
merge xs [] = xs
merge [] ys = ys
merge (x:xs) (y:ys) =
         if x < y
                 then x:(merge xs (y:ys))
                 else y:(merge (x:xs) ys)

msort :: [Int] -> [Int]
msort [] = []
msort xs 
    | length xs <= 1 = xs
    | otherwise      = merge (msort fst(halve xs)) (msort snd(halve xs))

In the msort main body, my understanding of how it should work is that if the length of xs is less than or equal to 1 then it returns the list. Otherwise, it halves the list xs and recursively starts mosrt again, until length is equal to or less than 1, at which point it applies merge to it.

What am I missing / how is that wrong?

Any help is appreciated :)

Answer 1

You forgot brackets in your recursive msort calls:

msort :: [Int] -> [Int]
msort xs 
    | length xs <= 1 = xs
    | otherwise = merge (msort (fst (halve xs))) (msort (snd (halve xs)))

That being said, using length is often not a good idea, since it runs in O(n). It is better to use pattern matching here. Furthermore you can use a where clause to avoid calculating halve xs twice:

msort :: Ord a => [a] -> [a]
msort [] = []
msort [x] = [x]
msort xs = merge (msort la) (msort lb)
    where (la, lb) = halve xs

The halve can be constructed where we pass every second element to one of the elements of the 2-tuple, like:

halve :: [a] -> ([a], [a])
halve [] = ([], [])
halve (x:xs) = (x:ya, yb)
    where (yb, ya) = halve xs

or with a foldr pattern:

halve :: [a] -> ([a], [a])
halve = foldr (\x (yb, ya) -> (x:ya, yb)) ([], [])

and the merge can be implemented more elegantly by using as-patterns:

merge :: Ord a => [a] -> [a] -> [a]
merge [] ys = ys
merge xs [] = xs
merge xa@(x:xs) ya@(y:ys)
    | x <= y = x : merge xs ya
    | otherwise = y : merge xa ys