Haskell merge sort with two merging functions asc and desc

Question

I would like to make use of the merge sort algorithm. The mergeSort is the main function which awaits the merging function as the first parameter. Does anyone have an idea, where is the issue in my case? Thank you very much in advance.

mergeSort xs = merge xs
mergeDesc xs = reverse (mergeAsc xs)
mergeAsc [] = []
mergeAsc [x] = [x]
mergeAsc xs = merge (mergeAsc top) (mergeAsc bottom) where (top, bottom) = splitAt (length xs `div` 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

Answer 1

Add type signatures to your functions, then the problem becomes obvious:

mergeAsc, mergeDesc :: Ord a => [a] -> [a]

mergeDesc xs = reverse (mergeAsc xs)
mergeAsc [] = []
mergeAsc [x] = [x]
mergeAsc xs = merge (mergeAsc top) (mergeAsc bottom) where (top, bottom) = splitAt (length xs `div` 2) xs

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

So, if you define mergeSort as merge, it's a function that merely merges two ordered lists, when you actually want it to order a single list. You can achieve that with

mergeSort xs = mergeAsc xs

or simply and preferrably,

mergeSort = margeAsc

---

Note that mergeDesc isn't really nice: you first sort the list in the wrong order, and then reverse it? In Haskell, you want your algorithms to be flexible enough to handle stuff like different orderings by themselves. So you would define

mergeSortBy :: (a->a->Ordering) -> [a] -> [a]
mergeSortBy cmp = mSort
 where 
       mSort [] = []
       mSort [x] = [x]
       mSort xs = merge (mSort top) (mSort bottom)
        where (top, bottom) = splitAt (length xs `quot` 2) xs

       merge [] ys = ys
       merge xs [] = xs
       merge (x:xs) (y:ys) = case x`cmp`y of
          LT  -> x : merge xs (y:ys)
          _   -> y : merge (x:xs) ys

Then you can simply define mergeSort = mergeSortBy compare, and mergeSortDesc = mergeSortBy (flip compare).

Also observe how making merge a local function prevents the error you had in your implementation.

---

and it says it should be declared as: mergeSort :: ([a]->[a]->[a]) -> [a] -> [a] as the function that accepts the merging function as the first argument...

That's strange, it shouldn't be called mergeSort then but sortWithMerge or something. Anyway, it's simple enough to do that: just throw out cmp (which is only used in the merge subfunction!) and replace it with merge as an argument instead of defining that locally.

sortWithMerge :: ([a]->[a]->[a]) -> [a] -> [a]
sortWithMerge merger = mSort
 where 
       mSort [] = []
       mSort [x] = [x]
       mSort xs = merger (mSort top) (mSort bottom)
        where (top, bottom) = splitAt (length xs `quot` 2) xs