I have to admit that I didn’t fully understand the apfelmus example code. Nevertheless, I made an effort to address both of his criticisms:

- The merge() function does not use an accumulator argument any more and is indeed much simpler now.
- The recursive
`mergesort_`

function now does not use the haskell list `length`

operator any more. Instead, the length of the list to be sorted is passed down the recursive chain.

Please see the optimised mergesort implementation for details.

These improvements reduced the RAM utilisation and improved the run-time performance by another 20% respectively.

Nothing to scoff at, eh?

### Like this:

Like Loading...

*Related*

You can possibly do better by writing a simple function to find the middle of the list in one pass without using length.

The trick is to maintain two pointers, and move one ahead twice as fast as the other.

findMiddle [] [] = ([], [])

findMiddle (x:xs) [] = ([x], xs)

findMiddle (x:xs) (_:[]) = ([x], xs)

findMiddle (x:xs) (_:_:ys) = (x:xs’, ys’)

where (xs’, ys’) = findMiddle xs ys

that’s the idea, I think it’s got an off-by-1 error somewhere in there.

To understand the different approaches to dividing the list, you can use a dummy

`merge`

and have a look at the resulting treeimport Data.Tree

leaf x = Node (“[“++show x++”]”) []

merge a b = Node “merge” [a,b]

empty = Node “[]” []

In other words, the

`mergesort`

s won’t sort a list anymore but instead return a tree that shows how the calls to`merge`

are nested. Use`drawTree`

to print it.— apelmus’ version

mergesortA [] = empty

mergesortA xs = foldtree1 merge $ map leaf xs

foldtree1 f [x] = x

foldtree1 f xs = foldtree1 f $ pairs xs

where

pairs (x:x’:xs) = f x x’ : pairs xs

pairs xs = xs

— muharem’s version

mergesortB xs = mergesort’ xs (length xs)

where

mergesort’ [] 0 = empty

mergesort’ [x] 1 = leaf x

mergesort’ xs n = merge (mergesort’ ls ln) (mergesort’ rs rn)

where

(ls,rs) = splitAt middle xs

middle = n `div` 2

(ln,rn) = (middle, n – middle)

— mrd’s version

mergesortC [] = empty

mergesortC [x] = leaf x

mergesortC xs = merge (mergesortC ls) (mergesortC rs)

where (ls,rs) = findMiddle xs xs

findMiddle xs [] = ([], xs)

findMiddle xs (_:[]) = ([], xs)

findMiddle (x:xs) (_:_:ys) = (x:xs’, ys’)

where (xs’, ys’) = findMiddle xs ys

Eeek, wordpress ate my

`pre`

tags 😦Hi. How your project develops?