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

[Bernie Pope]

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.

Cheers,
Bernie.