fastSort benchmarking (was Re: Work done so far)

[Christopher Wright]

Robert Fraser wrote:
> Matti Niemenmaa wrote:
>> It appears to do a lot of comparing, though---and thus, when made to 
>> use a custom comparing function instead of the built-in "<" operator 
>> it quickly slows down.
> 
> Mergesort generally does fewer compares than quicksort (that's why it's 
> the default sorting algorithm for objects, but not primitives, in Java), 
> although it has the cost of copying & allocation there.

There are in-place merge sorts, though I'm not sure how costly it is to 
do that. One implementation I see right now will cost O(n * n * log n) 
in the worst case, which is clearly unacceptable.