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

[apfelmus]

>> 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

    http://en.wikipedia.org/wiki/Sorting_network


Regards,
apfelmus