ch-ch-changes

[Andrei Alexandrescu]

Christopher Wright wrote:
> 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.

Good point.

Andrei