Is the merge sort sort implementation good?

Question

I just started learning Haskell last night, and I had never used a functional programming language before. I just want to know if my merge option is good or bad, and what is good or bad. Maybe this is even wrong? Well, that sounds like sorting, but maybe the Algorithm is not what I think merge sorting is.

Just tell me everything that I could improve here. I myself consider it a fairly clear and simple implementation. Thanks for your advice, here is the code :)

merge [] ys = ys merge xs [] = xs merge xs ys = sorted : merge left right where sorted = if head(xs) < head(ys) then head(xs) else head(ys) left = if head(xs) <= head(ys) then tail(xs) else xs right = if head(xs) > head(ys) then tail(ys) else ys msort [] = [] msort [x] = [x] msort xs = merge (msort left) (msort right) where left = take (div (length xs) 2) xs right = drop (div (length xs) 2) xs 

Answer 1

Well, firstly, we can rewrite the merge to be a little more elegant using pattern matching

 merge [] ys = ys merge xs [] = xs merge xs@ (x:xs1) ys@ (y:ys1) | x <= y = x : merge xs1 ys | otherwise = y : merge xs ys1 

In general, you should avoid using head and tail , as they are a little dangerous (they cause an error for an empty list) and, if possible, use pattern matching.

The implementation of msort largely depends on the fact that we can split the list in a more efficient way. This is because length xs - terminates O (N). The compiler can save you and cache the result of calling length so that the second call to length does not move the list again. But take and drop will pretty much trigger two more workarounds, thus breaking the list using 3 workarounds that can be expensive. We can achieve more by dividing the list in two lists: the first one containing elements at odd positions, and the second list with elements placed at even positions, for example:

 msort [] = [] msort [x] = [x] msort xs = merge (msort first) (msort second) where (first, second) = splitInHalves xs splitInHalves [] = ([], []) splitInHalves [x] = ([x], []) splitInHalves (x:y:xs) = let (xs1, ys1) = splitInHalves xs in (x:xs1, y:ys1) 

This gives you the same value of Sort by volume O (NlogN). It feels different because you are likely to use it locally (by changing the original list) in an imperative language such as C. This version is a bit more expensive in memory, but has its advantages - it’s easier to talk about, so it’s more convenient to maintain , and it’s also very easy to parallelize without worrying about anything other than the algorithm itself, which is what a good programming language should include for developers who use it.

EDIT 1:

If the syntax is a bit, here are some resources:

• Matching pattern - a bit with the @ symbol is called as-pattern. You will find him there.
• let is the keyword used to declare the variable to be used in the subsequent expression (whereas where binds the variable in the preceding expression). More information on Haskell syntax, including guards (things with | condition = value ), can be found here in this chapter Learn You a Haskell

EDIT 2:

@ is7s proposed a more compressed version of splitInHalves using the foldr function:

 splitInHalves = foldr (\x (l,r) -> (x:r,l)) ([],[]) 

EDIT 3:

Here is another answer that provides an alternative merge sort implementation that also has a stable property:

lazy assessment and time complexity

Hope this helps and welcomes the wonderful world of functional programming!