3 Apr
2008
3 Apr
'08
11:37 a.m.
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