[Haskell-cafe] Re: Sorting with a weaker form of Ord (Re: Type constraints for class instances)

apfelmus 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 mailing list