[Haskell-cafe] will the real quicksort please stand up? (or:
sorting a > million element list)
bjpop at csse.unimelb.edu.au
Tue Oct 23 02:00:11 EDT 2007
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.
More information about the Haskell-Cafe