Weird profiling behaviour

Ketil Z. Malde
27 Jun 2002 11:10:59 +0200

Colin Runciman <> writes:

> 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.

*lights go on*

Of course!  While I have about 90K values to sort, it's only a range
from 0 to about 5-600, and a less than even distribution at that.  (I
must be a lot denser than I thought. Colin, if you ever happen to pass
by, do let me know, I think I owe you a beer.) 

Okay: bucket sort; does anybody know of a nice bucket sort I can rip
off?  :-)  (Actually, while I haven't done the math or the tests to
say for sure, I suspect a trivial mod to QS where equals are kept in a
separate list might do just fine.  Would that be a sensible
modification to put in the standard libraries, I wonder?)

Thanks again!

If I haven't seen further, it is by standing in the footprints of giants