Simon Marlow
Thu, 27 Jun 2002 11:41:50 +0100

>  | 5.02 uses quicksort, but 5.04 will use mergesort
>  | instead which has much more predictable performance
>  | behaviour.
> 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:

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.