ch-ch-changes

[Christopher Wright]

Andrei Alexandrescu wrote:
> A stride is a great way to get a good pivot into a large array when 
> sorting. You sort the stride and then get its median.

I'm not so sure about that. If the array is in fact large, you're 
dealing with an external memory situation, and sorting the stride means 
you have to touch every single block of the array. If your stride is 
even larger than a block, you could change this, but caches are all 
designed around sequential access, so they'll defeat you even if you are 
that clever.

So, using the stride of an array to find a pivot will double the amount 
of time it takes to sort the array in the worst case.