Simon Marlow <[EMAIL PROTECTED]> writes:
> > 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.
Sergey gave a suggestion (backed by numbers) for a better algorithm.
I would say (and I think Sergey would too) that the standard library
should provide an O(n log(n)) sorting algorithm, rather than an
algorithm which is O(n log(n)) for some applications and O(n^2) for
others (even if the first algorithm is a constant factor of two or
three slower than the best case of the second). Sometimes
applications do need to sort lists which are nearly sorted, or which
may be already sorted...
Carl Witty
[EMAIL PROTECTED]
