Weird profiling behaviour

Colin Runciman colin@cs.york.ac.uk
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
>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