On Wednesday 26 June 2002 04:19 am, Colin Runciman wrote: > Could it be that the string-comparison sort simply has less sorting to do > than the int-comparison sort? The default definition of sortBy uses > insertion sort, so if the string-sort input happens to be already sorted > it takes linear time and if the int-sort input happens to be in > reverse order it takes quadratic time.
A question I would like to ask is which compiler and libraries are you using? In the December 2001 version of Hugs, sortBy is implemented with the default definition of insertion sort. But if you are using ghc, you are probably using a quicksort algorithm. (Recently the ghc libraries were switched to use mergesort instead, but I'm not sure whether this made it into any of the released versions.) Remember that quicksort behaves quadratically in the worst case, which can happen with pre-sorted input. Maybe this can explain why the second round of sorting is so slow? - Brian Huffman _______________________________________________ Glasgow-haskell-users mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/glasgow-haskell-users