Haskell Merging multiple lists

Question

I want to write a merge function that takes multiple x sorted lists and merges them into just one sorted list by incremental values (smallest to largest). I think I can do two lists and combine into one, but can't figure out the base case for multiple lists and combining into one sorted.

merge :: [[a]] -> [a]

Answer 1

Maybe a faster implementation:

mergeTwo :: Ord a => [a] -> [a] -> [a]
mergeTwo x [] = x
mergeTwo [] x = x
mergeTwo (x:xs) (y:ys) = if x < y
                          then x:(mergeTwo xs (y:ys))
                          else y:(mergeTwo (x:xs) ys)

mergePairs :: Ord a => [[a]] -> [[a]]
mergePairs [] = []
mergePairs (x:[]) = [x]
mergePairs (x:y:tail) = mergePairs ((mergeTwo x y):(mergePairs tail))

mergeAll :: Ord a => [[a]] -> [a]
mergeAll [] = []
mergeAll x = head $ mergePairs x

mergeTwo just merges two lists. mergeAll just runs mergePairs and returns head if there is some. Magic happens in mergePairs, which takes list of lists and merges pairs, than does this again and so on, while there are at least two lists.

It might be faster, imagine you are running

merge = foldl merge2 []

It takes one long list and merges and merges. If you run it at [[1,2,3],[4,5,6],[7,8,9],[10,11,12]], it merges:

[] with [1,2,3]

[1,2,3] with [4,5,6]

[1,2,3,4,5,6] with [7,8,9]

[1,2,3,4,5,6,7,8,9] with [10,11,12]

But you want to keep lists of approx same lenght. So you want to merge:

[1,2,3] with [4,5,6]

[7,8,9] with [10,11,12]

[1,2,3,4,5,6] with [7,8,9,10,11,12]

You could also consider paraller implementation of mergePairs, it could be useful on multicore processors. But I have no experience in this :/

Answer 2

If you can define the function for two lists, then you can generalize it to arbitrarily many lists by simply going through each sublist and merging it with the current result until you've merge all the lists. This can be expressed as a fold like this:

merge = foldr merge2 []