> In addition to my previous note on the implementation of minimum and
> the like, could you also revise the List.sort implementation?
>
> For example, the merge sorting, it is 100 times cheaper on
> sort [1..6000]
> than what shows ghc-4.02.
> And again, i was forced to hide the ghc `sort'.
> The merge sorting costs O( n*log(n) ), so it is good in any case.
> Why not implement it?
GHC's sort implementation is a well-optimised quicksort plundered originally
from the hbc library I believe. In your example above you mention testing
it on an already sorted list, which is the worst case example for this
sorting algorithm, since it picks the first element of the list as the
paritition. Try some tests on random lists, I think you'll find GHC's sort
does rather better.
However, we're open to suggestions (backed up by numbers, of course) for a
better algorithm.
Cheers,
Simon
