[Haskell-cafe] Re: Sorting with a weaker form of Ord (Re: Type
constraints for class instances)
apfelmus at quantentunnel.de
Thu Apr 3 11:37:53 EDT 2008
>> Krzysztof Skrzętnicki wrote:
>>> class YOrd a where
>>> ycmp :: a -> a -> (a,a)
>>> Unfortunately, the performance of ysort is rather low. I believe that
>>> it is impossible to create any sorting algorithm that uses ycmp
>>> instead of compare, that is faster than O(n^2).
Ok, it is possible to be faster, namely O(n (log n)^2) and even better.
Sorting algorithms based on a comparator function like ycmp are called
"sorting networks" and in fact well-known. See also
More information about the Haskell-Cafe