mergesort

[Simon Marlow]

>  | 5.02 uses quicksort, but 5.04 will use mergesort
>  | instead which has much more predictable performance
>  | behaviour.
>=20
> What implementation of mergesort are you using? (Could you
> send me code?)

It's Ian Lynagh's implementation, from a thread on this list recently:

http://www.haskell.org/pipermail/glasgow-haskell-users/2002-May/003376.h
tml

There was some concern about the lack of laziness and stack overflows,
but the general concensus was that merge sort was a better choice.  Feel
free to argue otherwise :)

In the new libraries, I don't have any objection to providing both
Data.List.mergesort and Data.List.quicksort, and even
Data.List.insertionsort for almost-sorted lists.

Cheers,
	Simon