27 Jun
2002
27 Jun
'02
3:39 a.m.
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