Ketil Z. Malde wrote: >>5.02 uses quicksort, >> >That's funny, since I see quadratic scaling, I must be hitting worst >case both times? 'sort' and 'sortBy' *are* implemented in the same >way, right? > Implementations of QuickSort on lists usually take the easy option of using the head of the list as the threshold value for partitioning. As a consequence QuickSort does indeed degenerate to quadratic cost in the worst case.
Also, curiously enough, it could just as well be the problem that your int-sorting phase has too *little* sorting to do, as this common version of quickSort degenerates both for in-order and reverse-order inputs. Regards Colin R _______________________________________________ Glasgow-haskell-users mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
