I am new to Haskell and functional programming. I am trying to write the 3-way merge sort algorithm in Haskell. Problem is, when I run the code in GHCi it just returns *** Exception: stack overflow
. I have been trying to understand the problem, but I got no solution. If anyone can help, I would appreciate it. The code and the output is below.
-- three_way.hs
-- Merge function to merge three sorted lists
merge :: Ord a => [a] -> [a] -> [a] -> [a]
merge [] [] [] = []
merge left [] [] = left
merge [] left [] = left
merge [] [] right = right
merge left middle [] = merge left middle []
merge left [] right = merge left [] right
merge (l:ls) (m:ms) (r:rs)
| l <= m && l <= r = l : merge ls (m:ms) (r:rs)
| m <= l && m <= r = m : merge (l:ls) ms (r:rs)
| otherwise = r : merge (l:ls) (m:ms) rs
-- 3-way Merge Sort function
threeWayMergeSort :: Ord a => [a] -> [a]
threeWayMergeSort [] = []
threeWayMergeSort [x] = [x]
threeWayMergeSort xs = merge (threeWayMergeSort left) (threeWayMergeSort middle) (threeWayMergeSort right)
where
n = length xs
left = take (n `div` 3) xs
middle = take (n `div` 3) (drop (n `div` 3) xs)
right = drop (2 * (n `div` 3)) xs
$ ghci three_way.hs
GHCi, version 9.4.8: https://www.haskell.org/ghc/ :? for help
[1 of 2] Compiling Main ( three_way.hs, interpreted )
Ok, one module loaded.
ghci> threeWayMergeSort [2,1]
*** Exception: stack overflow
4
You make recursive calls without “progress”, like:
merge left middle [] = merge left middle []
merge left [] right = merge left [] right
this thus means that if you call merge [1] [2] []
, it just keeps calling merge [1] [2] []
.
You thus should in that case perform a 2-way merge.
1