Have a look at the Util module in '-syslib misc', it provides
a variety of sorting algorithms, including said merge sort.
If you want others, check out Ralf Hinze's pages at
http://www.informatik.uni-bonn.de/~ralf/
--Sigbjorn
> [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED]] writes:
>
> Carl R. Witty <[EMAIL PROTECTED]> writes
>
> >>> The merge sorting costs O( n*log(n) ), so it is good in any case.
> >>> Why not implement it?
> [...]
> > 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...
>
>
> Indeed, i voice for the merge sort - exactly for the reasons you give
> - adding that the merge sort fits well functional programming,
> expresses in small and clear program.
> But i cannot justify the whole solution rigorousely, neither would
> like to get into long discussion on this not so vital subject.
> My protest expresses simply in the form of
>
> import List hiding (sort )
> import Prelude hiding (minimum,maximum,sum,product)
> import DPrelude (sort,minimum,maximum,sum,product ...)
>
> QuickSort - it is desirable to be provided too (in the List standard
> library). Only - if it is really true that, like people say, its
> *average* expense is considerably lower than of the merge sort.
> --------------------------------------------------------------
> ---------
> But i propose for the Haskell-2 Standard Library
>
> sortBy :: Char -> (a->a->Bool) -> [a] -> [a]
> --mode p xs
> -- sort list by ordering predicate p
> For example,
> sortBy 'm' (<) [2,1,3,1] --> [1,1,2,3]
> sortBy 'm' (>) [2,1,3,1] --> [3,2,1,1]
> sortBy 'q' (>) [2,1,3,1] --> [3,2,1,1]
>
> The mode 'm' reserves for the merge sort, 'q' for quick sort.
> --------------------------------------------------------------
> ---------
>
>
> Regards.
>
> ------------------
> Sergey Mechveliani
> [EMAIL PROTECTED]
>
