Haskell: head . mergeSort (for min element) in linear time?

Question

In the HaskellWiki https://wiki.haskell.org/Performance/Laziness they introduce the merge-sort function as non-lazy

merge_sort []  = []
merge_sort [x] = [x]
merge_sort lst = let (e,o) = cleave lst 
              in merge (merge_sort e) (merge_sort o) where
 merge :: (Ord a) => [a] -> [a] -> [a]
 merge xs [] = xs
 merge [] ys = ys
 merge xs@(x:t) ys@(y:u)
     | x <= y    = x : merge t ys
     | otherwise = y : merge xs u

since you first have to recursively cleave the list

 cleave = cleave' ([],[]) where
 cleave' (eacc,oacc) [] = (eacc,oacc)
 cleave' (eacc,oacc) [x] = (x:eacc,oacc)
 cleave' (eacc,oacc) (x:x':xs) = cleave' (x:eacc,x':oacc) xs

and then, going up the reduction layers, merge these. So a merge-sort runs in n(log n) time. But the composition

min xs = head . merge_sort $ xs

supposedly runs in linear time. I can't see why, as you still have to cleave every sublist until you arrive at the singleton/empty lists and then merge these to guarantee the first element of the returned list is the smallest of all. What am I missing?

Answer 1

But lazyness still comes into play with the definitions like min xs = head . merge_sort $ xs. In finding the minimal element this way only the necessary amount of comparisons between elements will be performed (O(n) a.o.t. O(nlogn) comparisons needed to fully sort the whole list).

You are right, it will have a time complexity of O(n log(n)), however if you read the above paragraph carefully you will see, that it is talking about the amount of comparisons. Only O(n) comparisions will be performed, because every merge application only has to produce one element, so it only has to compare the first two elements of its arguments. So you get n/2 comparisons at the leaves of the recursion plus n/4 one level up, then n/4,... all the way up to the top-level of the recursion. If you work it out you get n-1 comparisons.