haskell mergesort implementation compiles but does not return anything

Question

Here is my implementation:

mergesort :: (Ord a) => [a] -> [a]
mergesort list = merge (mergesort (left list)) (mergesort (right list))
  where
    left xs = take (div (length xs) 2) xs
    right xs = drop (div (length xs) 2) xs
    merge [] ys = ys
    merge xs [] = xs
    merge (x:xs) (y:ys)
      | x <= y = x : merge xs (y:ys)
      | otherwise = y : merge (x:xs) ys

The code compiles but when I run it my machine crashes. What am I doing wrong?

Answer 1

You are missing base cases - so you get infinite recursion. Trying stepping through your example with lists like [] or [1] and you'll fall straight into the problem.

mergesort :: (Ord a) => [a] -> [a]
mergesort [] = []   -- < ADDED
mergesort [x] = [x] -- < ADDED
mergesort list = merge (mergesort (left list)) (mergesort (right list))
  where
    left xs = take (div (length xs) 2) xs
    right xs = drop (div (length xs) 2) xs
    merge [] ys = ys
    merge xs [] = xs
    merge (x:xs) (y:ys)
      | x <= y = x : merge xs (y:ys)
      | otherwise = y : merge (x:xs) ys