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?

Did your original code include the empty case? If not, please rollback that edit. and let Alec know so that he can remove references to that case in his answer. — Bakuriu
– Bakuriu, Commented Jun 30, 2016 at 9:52

Alec · Accepted Answer · 2016-06-30 00:17:20Z

2

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

answered Jun 30, 2016 at 0:17

Alec

32.5k7 gold badges73 silver badges120 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

haskell mergesort implementation compiles but does not return anything

1 Answer 1

Comments

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Related