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]
