[Haskell-cafe] will the real quicksort please stand up? (or: sorting a > million element list)

[Bertram Felgenhauer]

Bernie Pope wrote:
>
> On 23/10/2007, at 8:09 AM, Thomas Hartman wrote:
>>
>>
>> (Prelude sort, which I think is mergesort, just blew the stack.)
>
> GHC uses a "bottom up" merge sort these days.
>
> It starts off by creating a list of singletons, then it repeatedly merges 
> adjacent pairs of lists until there
> is only one list left.
>
> I was teaching sorting to my first year students, and I also bumped into 
> the stack overflow at one million elements, using GHC's merge sort.
>
> I have been meaning to look into the cause of this, but my suspicion is 
> that strictness (or lack thereof) might be an issue.

Interesting. One of the functions in GHC's merge sort implementation is

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

Swapping the first two lines appears to fix the problem. I'm not sure
why. The generated core only differs in the order of two cases for the
second and third argument of 'merge', so it comes down to the precise
STG semantics. Can anybody explain the difference?

Bertram