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 _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
