fastSort benchmarking (was Re: Work done so far)

[Sean Kelly]

Matti Niemenmaa wrote:
> 
> Key for understanding the numbers:
> 
> For each algorithm, the first column set is for random, the second for
> already sorted, the third for sorted and then reversed, and the fourth
> for "median-of-3 killer" data, specially crafted to bring worst-case
> behaviour in median-of-3 quicksorts. The Tango sort used to hit a stack
> overflow and thus isn't tested with them.

The ticket you linked has revised numbers for the Tango sort, if anyone
is interested.  Also, I think it's worth noting that the built-in sort
routine actually does call a function for comparison (TypeInfo.cmp) --
there's simply no way to override it for a particular type.  Given this,
the average performance of the built-in sort is really excellent.


Sean