Weird profiling behaviour
Thu, 27 Jun 2002 08:39:02 +0100
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
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